001package net.sf.cpsolver.studentsct; 002 003import java.text.DecimalFormat; 004import java.util.Comparator; 005import java.util.HashMap; 006import java.util.Iterator; 007import java.util.TreeSet; 008 009import 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 Tomáš Müller<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 */ 046public 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}