001 package net.sf.cpsolver.studentsct.check; 002 003 import java.util.Collection; 004 import java.util.Collections; 005 import java.util.Comparator; 006 import java.util.Enumeration; 007 import java.util.HashSet; 008 import java.util.Hashtable; 009 import java.util.Iterator; 010 import java.util.Map; 011 import java.util.TreeSet; 012 import java.util.Vector; 013 014 import net.sf.cpsolver.ifs.util.CSVFile; 015 import net.sf.cpsolver.studentsct.StudentSectioningModel; 016 import net.sf.cpsolver.studentsct.model.Assignment; 017 import net.sf.cpsolver.studentsct.model.Course; 018 import net.sf.cpsolver.studentsct.model.CourseRequest; 019 import net.sf.cpsolver.studentsct.model.Enrollment; 020 import net.sf.cpsolver.studentsct.model.FreeTimeRequest; 021 import net.sf.cpsolver.studentsct.model.Request; 022 import net.sf.cpsolver.studentsct.model.Section; 023 import net.sf.cpsolver.studentsct.model.Student; 024 025 /** 026 * This class looks and reports all cases when a student cannot obtain a complete schedule because of 027 * time assignments of the requested courses. Course and section limits are not checked. 028 * 029 * <br><br> 030 * 031 * Usage:<br> 032 * <code> 033 * InevitableStudentConflicts ch = new InevitableStudentConflicts(model);<br> 034 * if (!ch.check()) ch.getCSVFile().save(new File("inevitable-conflicts.csv")); 035 * </code> 036 * 037 * <br><br> 038 * Parameters: 039 * <table border='1'><tr><th>Parameter</th><th>Type</th><th>Comment</th></tr> 040 * <tr><td>InevitableStudentConflicts.DeleteInevitable</td><td>{@link Boolean}</td><td> 041 * If true, for each no-good (the smallest set of requests of the same student that cannot be 042 * assigned at the same time), the problematic request (i.e., the request that was not 043 * assigned by {@link StudentCheck}) is removed from the model. 044 * </td></tr> 045 * </table> 046 * 047 * <br><br> 048 * 049 * @version 050 * StudentSct 1.1 (Student Sectioning)<br> 051 * Copyright (C) 2007 Tomáš Müller<br> 052 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 053 * Lazenska 391, 76314 Zlin, Czech Republic<br> 054 * <br> 055 * This library is free software; you can redistribute it and/or 056 * modify it under the terms of the GNU Lesser General Public 057 * License as published by the Free Software Foundation; either 058 * version 2.1 of the License, or (at your option) any later version. 059 * <br><br> 060 * This library is distributed in the hope that it will be useful, 061 * but WITHOUT ANY WARRANTY; without even the implied warranty of 062 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 063 * Lesser General Public License for more details. 064 * <br><br> 065 * You should have received a copy of the GNU Lesser General Public 066 * License along with this library; if not, write to the Free Software 067 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 068 */ 069 public class InevitableStudentConflicts { 070 private static org.apache.log4j.Logger sLog = org.apache.log4j.Logger.getLogger(InevitableStudentConflicts.class); 071 private StudentSectioningModel iModel; 072 private CSVFile iCSVFile = null; 073 public static boolean sDebug = false; 074 private boolean iDeleteInevitable; 075 076 /** Constructor 077 * @param model student sectioning model 078 */ 079 public InevitableStudentConflicts(StudentSectioningModel model) { 080 iModel = model; 081 iCSVFile = new CSVFile(); 082 iCSVFile.setHeader(new CSVFile.CSVField[] { 083 new CSVFile.CSVField("NoGood"), 084 new CSVFile.CSVField("NrStud"), 085 new CSVFile.CSVField("StudWeight"), 086 new CSVFile.CSVField("1. Course"), 087 new CSVFile.CSVField("2. Course"), 088 new CSVFile.CSVField("3. Course"), 089 new CSVFile.CSVField("4. Course"), 090 new CSVFile.CSVField("5. Course") 091 }); 092 iDeleteInevitable = model.getProperties().getPropertyBoolean("InevitableStudentConflicts.DeleteInevitable", false); 093 } 094 095 /** Return student sectioning model */ 096 public StudentSectioningModel getModel() { 097 return iModel; 098 } 099 100 /** Return report */ 101 public CSVFile getCSVFile() { 102 return iCSVFile; 103 } 104 105 /** Check model for inevitable student conflicts */ 106 public boolean check() { 107 sLog.info("Checking for inevitable student conflicts..."); 108 Hashtable noGoods = new Hashtable(); 109 long studentWithoutCompleteSchedule = 0; 110 long inevitableRequests = 0; 111 double inevitableRequestWeight = 0.0; 112 long incompleteInevitableRequests = 0; 113 double incompleteInevitableRequestWeight = 0.0; 114 long total = 0; 115 Comparator simpleCmp = new Comparator() { 116 public int compare(Object o1, Object o2) { 117 return o1.toString().compareTo(o2.toString()); 118 } 119 }; 120 HashSet requests2remove = new HashSet(); 121 for (Enumeration e=getModel().getStudents().elements();e.hasMoreElements();) { 122 Student student = (Student)e.nextElement(); 123 sLog.debug(" Checking "+(++total)+". student "+student+"..."); 124 if (student.isComplete()) { 125 for (Enumeration f=student.getRequests().elements();f.hasMoreElements();) { 126 Request request = (Request)f.nextElement(); 127 if (request.getAssignment()==null) { 128 inevitableRequests++; 129 inevitableRequestWeight+=request.getWeight(); 130 } 131 } 132 } else { 133 StudentCheck ch = new StudentCheck(student.getRequests()); 134 ch.check(); 135 if (!ch.isBestComplete()) { 136 sLog.info(" Student "+student+" cannot have a complete schedule"); 137 studentWithoutCompleteSchedule++; 138 } 139 int idx = 0; 140 for (Enumeration f=student.getRequests().elements();f.hasMoreElements();idx++) { 141 Request request = (Request)f.nextElement(); 142 Enrollment enrollment = ch.getBestAssignment()[idx]; 143 if (enrollment==null) { 144 if (!ch.isBestComplete()) { 145 Vector noGood = noGood(student,ch,idx); 146 sLog.info(" Request "+request+" cannot be assigned"); 147 for (Enumeration g=noGood.elements();g.hasMoreElements();) { 148 Request r = (Request)g.nextElement(); 149 sLog.debug(" "+r); 150 Collection values = null; 151 if (r instanceof CourseRequest) { 152 values = ((CourseRequest)r).getEnrollmentsSkipSameTime(); 153 } else { 154 values = request.computeEnrollments(); 155 } 156 for (Iterator i=values.iterator();i.hasNext();) { 157 Enrollment en = (Enrollment)i.next(); 158 sLog.debug(" "+enrollment2string(en)); 159 } 160 } 161 if (iDeleteInevitable) { 162 requests2remove.add(request); //noGood.lastElement() 163 sLog.info(" -- request "+request+" picked to be removed from the model"); 164 } 165 TreeSet key = new TreeSet(simpleCmp); 166 for (Enumeration g=noGood.elements();g.hasMoreElements();) { 167 Request r = (Request)g.nextElement(); 168 if (r instanceof CourseRequest) { 169 key.add((Course)((CourseRequest)r).getCourses().firstElement()); 170 } else { 171 key.add("Free "+((FreeTimeRequest)r).getTime().getLongName()); 172 } 173 } 174 Object[] counter = (Object[])noGoods.get(key); 175 int ir = (counter==null?1:((Integer)counter[0]).intValue()+1); 176 double irw = (counter==null?0.0:((Double)counter[1]).doubleValue())+request.getWeight(); 177 noGoods.put(key, new Object[]{new Integer(ir), new Double(irw)}); 178 if (ch.canAssign(request, idx)) { 179 incompleteInevitableRequests++; 180 incompleteInevitableRequestWeight+=request.getWeight(); 181 } 182 } 183 inevitableRequests++; 184 inevitableRequestWeight+=request.getWeight(); 185 } 186 } 187 } 188 } 189 for (Iterator i=noGoods.entrySet().iterator();i.hasNext();) { 190 Map.Entry entry = (Map.Entry)i.next(); 191 TreeSet noGood = (TreeSet)entry.getKey(); 192 Object[] counter = (Object[])entry.getValue(); 193 Vector fields = new Vector(); 194 String courseStr = ""; 195 for (Iterator j=noGood.iterator();j.hasNext();) { 196 Object x = (Object)j.next(); 197 if (x instanceof Course) { 198 Course course = (Course)x; 199 courseStr += course.getName(); 200 } else 201 courseStr += x.toString(); 202 if (j.hasNext()) 203 courseStr += ", "; 204 } 205 fields.add(new CSVFile.CSVField(courseStr)); 206 fields.add(new CSVFile.CSVField(((Integer)counter[0]).intValue())); 207 fields.add(new CSVFile.CSVField(((Double)counter[1]).doubleValue())); 208 for (Iterator j=noGood.iterator();j.hasNext();) { 209 Object x = (Object)j.next(); 210 if (x instanceof Course) { 211 Course course = (Course)x; 212 Vector courses = new Vector(1); courses.add(course); 213 CourseRequest cr = new CourseRequest(-1, 0, false, new Student(-1), courses, false); 214 String field = course.getName(); 215 int idx = 0; 216 for (Iterator k=cr.getEnrollmentsSkipSameTime().iterator();k.hasNext();) { 217 if (idx++>20) { 218 field += "\n ..."; break; 219 } else { 220 field += "\n "+enrollment2string((Enrollment)k.next()); 221 } 222 } 223 fields.add(new CSVFile.CSVField(field)); 224 } else 225 fields.add(new CSVFile.CSVField(x.toString())); 226 } 227 iCSVFile.addLine(fields); 228 } 229 if (!requests2remove.isEmpty()) { 230 for (Iterator i=requests2remove.iterator();i.hasNext();) { 231 Request request = (Request)i.next(); 232 removeRequest(request); 233 } 234 } 235 sLog.info("Students that can never obtain a complete schedule: "+studentWithoutCompleteSchedule); 236 sLog.info("Inevitable student requests: "+inevitableRequests); 237 sLog.info("Inevitable student request weight: "+inevitableRequestWeight); 238 sLog.info("Inevitable student requests of students without a complete schedule: "+incompleteInevitableRequests); 239 sLog.info("Inevitable student request weight of students without a complete schedule: "+incompleteInevitableRequestWeight); 240 if (iCSVFile.getLines()!=null) 241 Collections.sort(iCSVFile.getLines(), new Comparator() { 242 public int compare(Object o1, Object o2) { 243 CSVFile.CSVLine l1 = (CSVFile.CSVLine)o1; 244 CSVFile.CSVLine l2 = (CSVFile.CSVLine)o2; 245 int cmp = Double.compare(l2.getField(1).toDouble(),l1.getField(1).toDouble()); 246 if (cmp!=0) return cmp; 247 return l1.getField(0).toString().compareTo(l2.getField(0).toString()); 248 } 249 }); 250 return (inevitableRequests==0); 251 } 252 253 /** Remove given request from the model */ 254 private void removeRequest(Request request) { 255 request.getStudent().getRequests().remove(request); 256 for (Enumeration e=request.getStudent().getRequests().elements();e.hasMoreElements();) { 257 Request r = (Request)e.nextElement(); 258 if (r.getPriority()>request.getPriority()) 259 r.setPriority(r.getPriority()-1); 260 } 261 iModel.removeVariable(request); 262 if (request.getStudent().getRequests().isEmpty()) 263 iModel.getStudents().remove(request.getStudent()); 264 } 265 266 /** Convert given enrollment to a string (comma separated list of subpart names and time assignments only) */ 267 private static String enrollment2string(Enrollment enrollment) { 268 StringBuffer sb = new StringBuffer(); 269 Collection assignments = enrollment.getAssignments(); 270 if (enrollment.isCourseRequest()) { 271 assignments = new TreeSet(new Comparator() { 272 public int compare(Object o1, Object o2) { 273 Section s1 = (Section)o1; 274 Section s2 = (Section)o2; 275 return s1.getSubpart().compareTo(s2.getSubpart()); 276 } 277 }); 278 assignments.addAll(enrollment.getAssignments()); 279 } 280 for (Iterator i=assignments.iterator();i.hasNext();) { 281 Assignment a = (Assignment)i.next(); 282 if (a instanceof Section) 283 sb.append(((Section)a).getSubpart().getName()+" "); 284 if (a.getTime()!=null) 285 sb.append(a.getTime().getLongName()); 286 if (i.hasNext()) sb.append(", "); 287 } 288 return sb.toString(); 289 } 290 291 /** No-good set of requests 292 * @param student student 293 * @param ch student checked that failed to find a complete schedule 294 * @param idx index of unassigned course in the best found schedule 295 * @return the smallest set of requests that cannot be assigned all together, containing the request with the given index 296 */ 297 private Vector noGood(Student student, StudentCheck ch, int idx) { 298 Vector noGood = new Vector(); 299 Request rx = (Request)student.getRequests().elementAt(idx); 300 for (int i=0;i<student.getRequests().size();i++) { 301 if (i==idx) noGood.add(rx); 302 else if (ch.getBestAssignment()[i]!=null) noGood.add(ch.getBestAssignment()[i].getRequest()); 303 } 304 for (Enumeration e=noGood.elements();e.hasMoreElements();) { 305 Request r = (Request)e.nextElement(); 306 if (r.equals(rx)) continue; 307 Vector newNoGood = new Vector(noGood); 308 newNoGood.remove(r); 309 StudentCheck chx = new StudentCheck(newNoGood); 310 chx.check(); 311 if (!chx.isBestComplete()) noGood = newNoGood; 312 } 313 return noGood; 314 } 315 316 /** Use branch&bound technique to find out whether a student can get a complete schedule. */ 317 public static class StudentCheck { 318 private Vector iRequests; 319 private Enrollment[] iAssignment, iBestAssignment; 320 private Hashtable iValues; 321 private int iBestNrAssigned = 0; 322 private boolean iBestComplete = false; 323 324 /** 325 * Constructor 326 * @param requests course and free time requests of a student 327 */ 328 public StudentCheck(Vector requests) { 329 iRequests = requests; 330 } 331 332 /** 333 * Execute branch & bound, return the best found schedule for the selected student. 334 */ 335 public void check() { 336 iAssignment = new Enrollment[iRequests.size()]; 337 iBestAssignment = null; iBestNrAssigned = 0; iBestComplete = false; 338 iValues = new Hashtable(); 339 backTrack(0); 340 } 341 342 /** Best schedule */ 343 public Enrollment[] getBestAssignment() { 344 return iBestAssignment; 345 } 346 347 /** Number of requests assigned in the best schedule */ 348 public int getBestNrAssigned() { 349 return iBestNrAssigned; 350 } 351 352 /** Bound for the number of assigned requests in the current schedule */ 353 public int getNrAssignedBound(int idx) { 354 int bound = 0; 355 int i=0, alt=0; 356 for (Enumeration e=iRequests.elements();e.hasMoreElements();i++) { 357 Request r = (Request)e.nextElement(); 358 if (i<idx) { 359 if (iAssignment[i]!=null) 360 bound++; 361 if (r.isAlternative()) { 362 if (iAssignment[i]!=null || (r instanceof CourseRequest && ((CourseRequest)r).isWaitlist())) alt--; 363 } else { 364 if (r instanceof CourseRequest && !((CourseRequest)r).isWaitlist() && iAssignment[i]==null) alt++; 365 } 366 } else { 367 if (!r.isAlternative()) 368 bound ++; 369 else if (alt>0) { 370 bound ++; alt--; 371 } 372 } 373 } 374 return bound; 375 } 376 377 /** True when the best enrollment is complete */ 378 public boolean isBestComplete() { 379 return iBestComplete; 380 } 381 382 /** Save the current schedule as the best */ 383 public void saveBest() { 384 if (iBestAssignment==null) 385 iBestAssignment = new Enrollment[iAssignment.length]; 386 iBestNrAssigned = 0; 387 for (int i=0;i<iAssignment.length;i++) { 388 iBestAssignment[i] = iAssignment[i]; 389 if (iBestAssignment[i]!=null) iBestNrAssigned++; 390 } 391 int nrRequests = 0; 392 int nrAssignedRequests = 0; 393 int idx = 0; 394 for (Enumeration e=iRequests.elements();e.hasMoreElements();idx++) { 395 Request r = (Request)e.nextElement(); 396 if (!(r instanceof CourseRequest)) continue; //ignore free times 397 if (!r.isAlternative()) nrRequests++; 398 if (iBestAssignment[idx]!=null) nrAssignedRequests++; 399 } 400 iBestComplete = (nrAssignedRequests==nrRequests); 401 } 402 403 /** First conflicting enrollment */ 404 public Enrollment firstConflict(Enrollment enrollment) { 405 for (int i=0;i<iAssignment.length;i++) { 406 if (iAssignment[i]!=null && iAssignment[i].isOverlapping(enrollment)) return iAssignment[i]; 407 } 408 return null; 409 } 410 411 /** True if the given request can be assigned */ 412 public boolean canAssign(Request request, int idx) { 413 if (!request.isAlternative() || iAssignment[idx]!=null) return true; 414 int alt = 0; 415 int i = 0; 416 for (Enumeration e=iRequests.elements();e.hasMoreElements();i++) { 417 Request r = (Request)e.nextElement(); 418 if (r.equals(request)) continue; 419 if (r.isAlternative()) { 420 if (iAssignment[i]!=null || (r instanceof CourseRequest && ((CourseRequest)r).isWaitlist())) alt--; 421 } else { 422 if (r instanceof CourseRequest && !((CourseRequest)r).isWaitlist() && iAssignment[i]==null) alt++; 423 } 424 } 425 return (alt>0); 426 } 427 428 /** Number of assigned requests in the current schedule */ 429 public int getNrAssigned() { 430 int assigned = 0; 431 for (int i=0;i<iAssignment.length;i++) 432 if (iAssignment[i]!=null) assigned++; 433 return assigned; 434 } 435 436 /** branch & bound search */ 437 public void backTrack(int idx) { 438 if (sDebug) sLog.debug("BT["+idx+"]: -- assigned:"+getNrAssigned()+", bound:"+getNrAssignedBound(idx)+", best:"+getBestNrAssigned()); 439 if (idx==iAssignment.length) { 440 if (iBestAssignment==null || getNrAssigned()>getBestNrAssigned()) { 441 saveBest(); 442 if (sDebug) sLog.debug("BT["+idx+"]: -- BEST "+getBestNrAssigned()); 443 } 444 return; 445 } else if (isBestComplete() || getNrAssignedBound(idx)<=getBestNrAssigned()) { 446 if (sDebug) sLog.debug("BT["+idx+"]: -- BOUND "+getNrAssignedBound(idx)+" <= "+getBestNrAssigned()); 447 return; 448 } 449 Request request = (Request)iRequests.elementAt(idx); 450 if (sDebug) sLog.debug("BT["+idx+"]: -- REQUEST "+request); 451 if (!canAssign(request, idx)) { 452 if (sDebug) sLog.debug("BT["+idx+"]: -- CANNOT ASSIGN"); 453 backTrack(idx+1); 454 return; 455 } 456 Collection values = null; 457 if (request instanceof CourseRequest) { 458 CourseRequest courseRequest = (CourseRequest)request; 459 values = (Collection)iValues.get(courseRequest); 460 if (values==null) { 461 values = courseRequest.getEnrollmentsSkipSameTime(); 462 iValues.put(courseRequest, values); 463 } 464 } else { 465 values = request.computeEnrollments(); 466 } 467 if (sDebug) sLog.debug("BT["+idx+"]: -- VALUES: "+values.size()); 468 boolean hasNoConflictValue = false; 469 for (Iterator i=values.iterator();i.hasNext() && !isBestComplete();) { 470 Enrollment enrollment = (Enrollment)i.next(); 471 if (sDebug) sLog.debug("BT["+idx+"]: -- "+enrollment2string(enrollment)); 472 Enrollment conflict = firstConflict(enrollment); 473 if (conflict!=null) { 474 if (sDebug) sLog.debug("BT["+idx+"]: -- conflict with "+conflict.getRequest()+" "+enrollment2string(conflict)); 475 continue; 476 } 477 hasNoConflictValue = true; 478 iAssignment[idx] = enrollment; 479 backTrack(idx+1); 480 iAssignment[idx] = null; 481 } 482 if (!hasNoConflictValue || request instanceof CourseRequest) { 483 if (sDebug) sLog.debug("BT["+idx+"]: -- without assignment"); 484 backTrack(idx+1); 485 } 486 } 487 } 488 489 }