001 package net.sf.cpsolver.studentsct;
002
003 import java.text.DecimalFormat;
004 import java.util.Comparator;
005 import java.util.Hashtable;
006 import java.util.Iterator;
007 import java.util.TreeSet;
008
009 /**
010 * A test class to demonstrate and compare different online sectioning approaches.
011 * It assumes only a single course with just one instructional type (subpart) and
012 * that we know the correct expected demand in advance.
013 * <br><br>
014 * With the given configuration (e.g., two sections of size 5), it tries all
015 * combinations of students how they can be enrolled and compute average and worst
016 * case scenarios.
017 * <br><br>
018 * Execution:<br>
019 * java -cp cpsolver-all-1.1.jar
020 * net.sf.cpsolver.studentsct.OnlineSectProof n1 n2 n3 ...<br>
021 * where n1, n2, etc. are the sizes of particular sections, e.g., 10 10 for two sections of size 10.
022 * <br><br>
023 *
024 * @version
025 * StudentSct 1.1 (Student Sectioning)<br>
026 * Copyright (C) 2007 Tomáš Müller<br>
027 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
028 * Lazenska 391, 76314 Zlin, Czech Republic<br>
029 * <br>
030 * This library is free software; you can redistribute it and/or
031 * modify it under the terms of the GNU Lesser General Public
032 * License as published by the Free Software Foundation; either
033 * version 2.1 of the License, or (at your option) any later version.
034 * <br><br>
035 * This library is distributed in the hope that it will be useful,
036 * but WITHOUT ANY WARRANTY; without even the implied warranty of
037 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
038 * Lesser General Public License for more details.
039 * <br><br>
040 * You should have received a copy of the GNU Lesser General Public
041 * License along with this library; if not, write to the Free Software
042 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
043 */
044 public class OnlineSectProof {
045 private static DecimalFormat sDF = new DecimalFormat("0.000");
046
047 /** A representation of a long number of given base.*/
048 public static class Sequence {
049 private int iBase;
050 private int[] iSequence;
051 private int[] iCnt;
052
053 /**
054 * Constructor
055 * @param length size of the vector
056 * @param base base (e.g., 2 for a binary vector)
057 */
058 public Sequence(int length, int base) {
059 iSequence = new int[length];
060 for (int i=0;i<iSequence.length;i++)
061 iSequence[i]=0;
062 iCnt = new int[base];
063 for (int i=0;i<iCnt.length;i++)
064 iCnt[i]=0;
065 iCnt[0]=length;
066 iBase = base;
067 }
068
069 /** Increment vector by 1, returns false it flips from the highest possible number to zero */
070 public boolean inc() {
071 return inc(0);
072 }
073
074 /** Base of the sequence */
075 public int base() {
076 return iBase;
077 }
078
079 private boolean inc(int pos) {
080 if (pos>=iSequence.length) return false;
081 iCnt[iSequence[pos]]--;
082 iSequence[pos] = (iSequence[pos]+1)%iBase;
083 iCnt[iSequence[pos]]++;
084 if (iSequence[pos]==0) return inc(pos+1);
085 return true;
086 }
087
088 /** Count number of occurrences of given number in the sequence */
089 public int count(int i) {
090 return iCnt[i];
091 }
092
093 /** Size of the sequence */
094 public int size() {
095 return iSequence.length;
096 }
097
098 /** Return number on the given position, zero is the number of the least significant value, size()-1 is the highest one */
099 public int seq(int i) {
100 return iSequence[i];
101 }
102
103 /** Set the sequence from a string representation (A..0, B..1, C..2, etc.) */
104 public void set(String seq) {
105 for (int i=0;i<iCnt.length;i++)
106 iCnt[i]=0;
107 for (int i=0;i<iSequence.length;i++) {
108 iSequence[i]=(int)(seq.charAt(i)-'A');
109 iCnt[iSequence[i]]++;
110 }
111 }
112
113 /** String representation (A..0, B..1, C..2, etc.) going from the least significant value to the highest */
114 public String toString() {
115 StringBuffer s = new StringBuffer();
116 for (int i=0;i<iSequence.length;i++)
117 s.append((char)('A'+iSequence[i]));
118 return s.toString();
119 }
120
121 /** If a sequence of all zeros is considered as 0, and the highest possible sequence (sequence of all base-1) is 1,
122 * this returns the position of the current sequence between these two bounds. */
123 public double progress() {
124 double ret = 0.0;
125 double mx = 1.0;
126 for (int i=size()-1;i>=0;i--) {
127 ret += mx * ((double)iSequence[i])/iBase;
128 mx *= 1.0/iBase;
129 }
130 return ret;
131 }
132
133 /** Category of a sequence, i.e., a string representation of the count of each number in the sequence. E.g.,
134 * A5B3C1 means that there are 5 zeros, 3 ones, and 1 two int the sequence.
135 */
136 public String cat() {
137 StringBuffer s = new StringBuffer();
138 for (int i=0;i<iBase;i++)
139 if (iCnt[i]>0) {
140 s.append((char)('A'+i));
141 s.append(iCnt[i]);
142 }
143 return s.toString();
144 }
145 }
146
147 /** Extension of {@link OnlineSectProof.Sequence} that represents an ordered set of students as they are to be enrolled into a course (given set of sections). */
148 public static class StudentSequence extends Sequence {
149 private int[] iColumns;
150 private int[] iMaxCnt;
151
152 /**
153 * Constructor
154 * @param columns limits of sections of a course (e.g., new int[] {5, 10} for two sections, first of the size 5, second of the size of 10)
155 */
156 public StudentSequence(int[] columns) {
157 super(length(columns), base(columns.length));
158 iColumns = columns;
159 iMaxCnt = new int[base()];
160 for (int i=0;i<iMaxCnt.length;i++)
161 iMaxCnt[i]=maxCnt(i);
162 }
163
164 /*
165 * Number of columns, i.e., number of sections in a course.
166 */
167 public int nrColumns() {
168 return iColumns.length;
169 }
170
171 /**
172 * Limit of a column (section of a course).
173 */
174 public int limit(int col) {
175 return iColumns[col];
176 }
177
178 /**
179 * Check that the underlying sequence is a valid sequence of students. I.e., that each student can be enrolled into a section.
180 * @return true, if valid
181 */
182 public boolean check() {
183 for (int i=0;i<base();i++)
184 if (maxCnt(i)<count(i)) return false;
185 for (int c=0;c<nrColumns();c++) {
186 int allowed = 0;
187 for (int i=0;i<size() && allowed<limit(c);i++)
188 if (allow(seq(i), c)) allowed++;
189 if (allowed<limit(c)) return false;
190 }
191 return true;
192 }
193
194 private static int length(int columns[]) {
195 int len = 0;
196 for (int i=0;i<columns.length;i++)
197 len += columns[i];
198 return len;
199 }
200 private static int base(int nrColumns) {
201 return (1<<nrColumns)-1;
202 }
203
204 /**
205 * Check whether it is possible to allow student of given type into the given section.
206 * Student type can be seen as a binary string that has 1 for each section into which a
207 * student can be enrolled. I.e., student of type 0 can be enrolled into the fist
208 * section, type 2 into the second section, type 3 into both first and section section,
209 * type 4 into the third section, type 5 into the first and third section etc.
210 */
211 public boolean allow(int x, int col) {
212 return ((x+1) & (1<<col))!=0;
213 }
214 /**
215 * Number of sections into which a student of a given type can be enrolled
216 * (see {@link OnlineSectProof.StudentSequence#allow(int, int)}).
217 */
218 public int nrAllow(int x) {
219 int ret = 0;
220 for (int i=0;i<nrColumns();i++)
221 if (allow(x,i)) ret ++;
222 return ret;
223 }
224 /**
225 * Maximum number of student of the given type that can be enrolled into the
226 * provided sections (i.e., sum of limits of sections that are allowed fot the
227 * student of the given type, see {@link OnlineSectProof.StudentSequence#allow(int, int)}).
228 */
229 public int maxCnt(int x) {
230 int ret = 0;
231 for (int i=0;i<nrColumns();i++)
232 if (allow(x,i)) ret += limit(i);
233 return ret;
234 }
235 }
236
237 /** Implemented online algorithms (heuristics) */
238 public static String sOnlineAlgs[] = new String[] {
239 "Max(Available)",
240 "Min(Used/Limit)",
241 "Min(Expected-Available)",
242 "Min(Expected/Available)",
243 "Min((Expected-Available)/Limit)",
244 "Min(Expected/(Available*Limit))"
245 };
246
247 /**
248 * Return true, if the given heuristics should be skipped (not evaluated).
249 * @param computeExpectations true, if expected demand should be computed in advance
250 * @param alg online algorithm (see {@link OnlineSectProof#sOnlineAlgs})
251 * @param allTheSame true, if all the sections are of the same size
252 * @return true if the given heuristics does not need to be computed (e.g., it is the same of some other)
253 */
254 public static boolean skip(boolean computeExpectations, int alg, boolean allTheSame) {
255 switch (alg) {
256 case 0:
257 return !computeExpectations;
258 case 1:
259 return !computeExpectations;
260 }
261 return false;
262 }
263
264 /**
265 * Implementation of the sectioning algorithms.
266 * @param limit section limit
267 * @param used number of space already used
268 * @param expected expected demand for the given section
269 * @param alg online algorithm (see {@link OnlineSectProof#sOnlineAlgs})
270 * @return value that is to be minimized (i.e., a section with the lowest number will be picked for the student)
271 */
272 public static double onlineObjective(double limit, double used, double expected, int alg) {
273 double available = limit - used;
274 switch (alg) {
275 case 0:
276 return -available;
277 case 1:
278 return used/limit;
279 case 2:
280 return expected-available;
281 case 3:
282 return expected/available;
283 case 4:
284 return (expected-available)/limit;
285 case 5:
286 return expected/(available*limit);
287 }
288 return 0.0;
289 }
290
291 /**
292 * Section given sequence of students into the course and return the number of students that cannot be sectioned.
293 * @param sq sequence of studends
294 * @param computeExpectations true, if expected demand for each section should be computed in advance (otherwise, it is initially set to zero)
295 * @param alg online algorithm (see {@link OnlineSectProof#sOnlineAlgs})
296 * @param debug if true, some debug messages are printed
297 * @return number of students that will not be sectioned in such a case
298 */
299 public static int checkOnline(StudentSequence sq, boolean computeExpectations, int alg, boolean debug) {
300 int used[] = new int[sq.nrColumns()];
301 double exp[] = new double[sq.nrColumns()];
302 for (int i=0;i<sq.nrColumns();i++) { used[i]=0; exp[i]=0.0; }
303 if (computeExpectations) {
304 for (int i=0;i<sq.size();i++) {
305 int x = sq.seq(i);
306 double ex = 1.0 / sq.nrAllow(x);
307 for (int c=0;c<sq.nrColumns();c++) {
308 if (!sq.allow(x, c)) continue;
309 exp[c]+=ex;
310 }
311 }
312 }
313 if (debug) {
314 StringBuffer sbExp = new StringBuffer();
315 StringBuffer sbUse = new StringBuffer();
316 for (int c=0;c<sq.nrColumns();c++) {
317 if (c>0) {
318 sbExp.append(",");
319 sbUse.append(",");
320 }
321 sbExp.append(sDF.format(exp[c]));
322 sbUse.append(used[c]);
323 }
324 System.out.println(" -- initial USE:["+sbUse+"], EXP:["+sbExp+"], SQ:"+sq.toString()+", ALG:"+sOnlineAlgs[alg]);
325 }
326 int ret = 0;
327 for (int i=0;i<sq.size();i++) {
328 int x = sq.seq(i);
329 int bestCol = -1;
330 double bestObj = 0.0;
331 for (int c=0;c<sq.nrColumns();c++) {
332 if (!sq.allow(x, c)) continue;
333 if (used[c]>=sq.limit(c)) continue;
334 double obj = onlineObjective(sq.limit(c),used[c], exp[c], alg);
335 if (debug) System.out.println(" -- test "+((char)('A'+x))+" --> "+(c+1)+" (OBJ="+sDF.format(obj)+")");
336 if (bestCol<0 || bestObj>obj) {
337 bestCol = c; bestObj = obj;
338 }
339 }
340 if (bestCol>=0) {
341 used[bestCol]++;
342 double ex = 1.0 / sq.nrAllow(x);
343 for (int c=0;c<sq.nrColumns();c++) {
344 if (!sq.allow(x, c)) continue;
345 exp[c]-=ex;
346 }
347 if (debug) {
348 StringBuffer sbExp = new StringBuffer();
349 StringBuffer sbUse = new StringBuffer();
350 for (int c=0;c<sq.nrColumns();c++) {
351 if (c>0) {
352 sbExp.append(",");
353 sbUse.append(",");
354 }
355 sbExp.append(sDF.format(exp[c]));
356 sbUse.append(used[c]);
357 }
358 System.out.println(" "+((char)('A'+x))+" --> "+(bestCol+1)+" (OBJ="+sDF.format(bestObj)+", USE:["+sbUse+"], EXP:["+sbExp+"])");
359 }
360 } else {
361 if (debug) System.out.println(" "+((char)('A'+x))+" --> FAIL");
362 ret++;
363 }
364 }
365 return ret;
366 }
367
368 /** Simple integer counter */
369 public static class Counter {
370 private int iCnt = 0;
371 /** A counter starting from zero */
372 public Counter() {}
373 /** A counter starting from the given number */
374 public Counter(int init) { iCnt = init; }
375 /** Increase counter by one */
376 public void inc() {
377 iCnt++;
378 }
379 /** Increase counter by the given value */
380 public void inc(int val) {
381 iCnt+=val;
382 }
383 /** Return counter value */
384 public int intValue() {
385 return iCnt;
386 }
387 }
388
389 /** Comparison of two categories */
390 public static class CatCmp implements Comparator {
391 Hashtable iWorstCaseCat, iTotalCat, iCountCat;
392 /**
393 * Constructor
394 * @param countCat table (category, number of sequences of that category)
395 * @param totalCat table (category, total number of students that were not sectioned of a sequence from this category)
396 * @param worstCaseCat (category, worst number of students that were not sectioned of a sequence from this category)
397 */
398 public CatCmp(Hashtable countCat, Hashtable totalCat, Hashtable worstCaseCat) {
399 iWorstCaseCat = worstCaseCat; iTotalCat = totalCat; iCountCat = countCat;
400 }
401 /**
402 * Higher number of not-sectioned students in the worst case goes first.
403 * If the same, higher average number of not-sectioned students goes first.
404 * If the same, compare by category.
405 */
406 public int compare(Object o1, Object o2) {
407 String c1 = (String)o1;
408 String c2 = (String)o2;
409 int wc1 = ((Integer)iWorstCaseCat.get(c1)).intValue();
410 int wc2 = ((Integer)iWorstCaseCat.get(c2)).intValue();
411 int cmp = Double.compare(wc2, wc1);
412 if (cmp!=0) return cmp;
413 int cc1 = ((Counter)iCountCat.get(c1)).intValue();
414 int tc1 = ((Counter)iTotalCat.get(c1)).intValue();
415 int cc2 = ((Counter)iCountCat.get(c2)).intValue();
416 int tc2 = ((Counter)iTotalCat.get(c2)).intValue();
417 cmp = Double.compare(((double)tc2)/cc2, ((double)tc1)/cc1);
418 if (cmp!=0) return cmp;
419 return c1.compareTo(c2);
420 }
421 }
422
423 /**
424 * Test given course (set of sections)
425 * @param args set of integers -- limits of each sections
426 */
427 public static void main(String[] args) {
428 int[] x = new int[args.length];
429 for (int i=0;i<args.length;i++)
430 x[i] = Integer.parseInt(args[i]);
431 if (args.length==0) x = new int[] {5, 5};
432 boolean categories = "true".equals(System.getProperty("cat","true"));
433 boolean allTheSameSize = true;
434 String filter = System.getProperty("filter");
435
436 StudentSequence sq = new StudentSequence(x);
437 System.out.println("base: "+sq.base());
438 System.out.println("columns:");
439 int sameSize = -1;
440 for (int col = 0; col<x.length; col++) {
441 System.out.println(" "+(col+1)+". column of limit "+sq.limit(col));
442 if (sameSize<0) sameSize=sq.limit(col);
443 else if (sameSize!=sq.limit(col)) allTheSameSize=false;
444 }
445 System.out.println("combinations:");
446 for (int i = 0; i<sq.base(); i++) {
447 System.out.println(" case "+(char)('A'+i)+": ");
448 System.out.println(" max: "+sq.maxCnt(i));
449 for (int col = 0; col<x.length; col++) {
450 if (sq.allow(i, col)) System.out.println(" "+(col+1)+". column allowed");
451 }
452 }
453
454 if (System.getProperty("check")!=null) {
455 sq.set(System.getProperty("check"));
456 if (System.getProperty("case")!=null) {
457 int i = Integer.parseInt(System.getProperty("case"))-1;
458 System.out.println("Online sectioning #"+(i+1)+" "+sOnlineAlgs[i/2]+((i%2)==0?"":" w/o precomputed expectations"));
459 checkOnline(sq, (i%2)==0, i/2, true);
460 } else {
461 for (int i=0;i<2*sOnlineAlgs.length;i++) {
462 if (skip((i%2)==0, i/2, allTheSameSize)) continue;
463 System.out.println("Online sectioning #"+(i+1)+" "+sOnlineAlgs[i/2]+((i%2)==0?"":" w/o precomputed expectations"));
464 checkOnline(sq, (i%2)==0, i/2, true);
465 }
466 }
467 return;
468 }
469
470 TreeSet[] worstCaseSq = new TreeSet[2*sOnlineAlgs.length];
471 int[] worstCase = new int[2*sOnlineAlgs.length];
472 int[] total = new int[2*sOnlineAlgs.length];
473 Hashtable[] worstCaseSqCat = new Hashtable[2*sOnlineAlgs.length];
474 Hashtable[] worstCaseCat = new Hashtable[2*sOnlineAlgs.length];
475 Hashtable[] totalCat = new Hashtable[2*sOnlineAlgs.length];
476 Hashtable[] countCat = new Hashtable[2*sOnlineAlgs.length];
477 for (int i=0;i<2*sOnlineAlgs.length;i++) {
478 total[i]=0; worstCase[i]=-1; worstCaseSq[i]=null;
479 worstCaseSqCat[i]=new Hashtable();
480 worstCaseCat[i]=new Hashtable();
481 totalCat[i]=new Hashtable();
482 countCat[i]=new Hashtable();
483 }
484 long nrCases = 0;
485 System.out.println("N="+sDF.format(Math.pow(sq.base(),sq.size())));
486 long t0 = System.currentTimeMillis();
487 long mark = System.currentTimeMillis();
488 long nc = 0, hc = 0;
489 do {
490 //System.out.println(sq+" (cat="+sq.cat()+", check="+sq.check()+")");
491 if ((filter==null || filter.equals(sq.cat())) && sq.check()) {
492 for (int i=0;i<2*sOnlineAlgs.length;i++) {
493 if (skip((i%2)==0, i/2, allTheSameSize)) continue;
494 int onl = checkOnline(sq, (i%2)==0, i/2, false);
495 total[i] += onl;
496 if (worstCaseSq[i]==null || worstCase[i]<onl) {
497 if (worstCaseSq[i]==null)
498 worstCaseSq[i] = new TreeSet();
499 else
500 worstCaseSq[i].clear();
501 worstCaseSq[i].add(sq.toString());
502 worstCase[i] = onl;
503 } else if (worstCase[i]==onl && onl>0 && worstCaseSq[i].size()<100) {
504 worstCaseSq[i].add(sq.toString());
505 }
506 if (categories) {
507 String cat = sq.cat();
508 Counter cc = (Counter)countCat[i].get(cat);
509 if (cc==null) {
510 countCat[i].put(cat,new Counter(1));
511 } else {
512 cc.inc();
513 }
514 if (onl>0) {
515 Counter tc = (Counter)totalCat[i].get(cat);
516 if (tc==null) {
517 totalCat[i].put(cat,new Counter(onl));
518 } else {
519 tc.inc(onl);
520 }
521 Integer wc = (Integer)worstCaseCat[i].get(cat);
522 if (wc==null || wc.intValue()<onl) {
523 worstCaseCat[i].put(cat, new Integer(onl));
524 worstCaseSqCat[i].put(cat, sq.toString());
525 }
526 }
527 }
528 }
529 nrCases ++; hc++;
530 }
531 nc++;
532 if ((nc%1000000) == 0) {
533 mark=System.currentTimeMillis();
534 double progress = sq.progress();
535 double exp = ((1.0-progress)/progress)*(mark-t0);
536 System.out.println(" "+sDF.format(100.0*progress)+"% done in "+sDF.format((mark-t0)/60000.0)+" min ("+sDF.format(exp/60000.0)+" min to go, hit "+sDF.format(100.0*hc/nc)+"%)");
537 }
538 } while (sq.inc());
539 System.out.println("Number of combinations:"+nrCases+" (hit "+sDF.format(100.0*hc/nc)+"%)");
540 for (int i=0;i<2*sOnlineAlgs.length;i++) {
541 if (skip((i%2)==0, i/2, allTheSameSize)) continue;
542 System.out.println("Online sectioning #"+(i+1)+" "+sOnlineAlgs[i/2]+((i%2)==0?"":" w/o precomputed expectations"));
543 System.out.println(" worst case: "+sDF.format((100.0*worstCase[i])/sq.size())+"% ("+worstCase[i]+" of "+sq.size()+", sequence "+worstCaseSq[i]+")");
544 System.out.println(" average case: "+sDF.format((100.0*total[i])/(sq.size()*nrCases))+"%");
545 sq.set((String)worstCaseSq[i].first());
546 checkOnline(sq, (i%2)==0, i/2, true);
547 TreeSet cats = new TreeSet(new CatCmp(countCat[i], totalCat[i], worstCaseCat[i]));
548 cats.addAll(totalCat[i].keySet());
549 for (Iterator j=cats.iterator();j.hasNext();) {
550 String cat = (String)j.next();
551 int cc = ((Counter)countCat[i].get(cat)).intValue();
552 int tc = ((Counter)totalCat[i].get(cat)).intValue();
553 int wc = ((Integer)worstCaseCat[i].get(cat)).intValue();
554 String wcsq = (String)worstCaseSqCat[i].get(cat);
555 System.out.println(" Category "+cat+" (size="+cc+")");
556 System.out.println(" worst case: "+sDF.format((100.0*wc)/sq.size())+"% ("+wc+" of "+sq.size()+", sequence "+wcsq+")");
557 System.out.println(" average case: "+sDF.format((100.0*tc)/(sq.size()*cc))+"%");
558 }
559 }
560 /*
561 sq.set("EEEBBBAAA");
562 System.out.println(sq+" (cat="+sq.cat()+", check="+sq.check()+")");
563 sq.set("CACACAAABB");
564 checkOnline(sq, true, 2, true);
565 */
566 }
567
568 }