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 }