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