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