001package org.cpsolver.studentsct.heuristics.selection; 002 003import java.text.DecimalFormat; 004import java.util.ArrayList; 005import java.util.Collection; 006import java.util.Collections; 007import java.util.ConcurrentModificationException; 008import java.util.HashMap; 009import java.util.HashSet; 010import java.util.LinkedList; 011import java.util.List; 012import java.util.ListIterator; 013import java.util.Map; 014import java.util.Set; 015 016 017import org.apache.log4j.Logger; 018import org.cpsolver.ifs.assignment.Assignment; 019import org.cpsolver.ifs.heuristics.NeighbourSelection; 020import org.cpsolver.ifs.model.InfoProvider; 021import org.cpsolver.ifs.model.Neighbour; 022import org.cpsolver.ifs.solution.Solution; 023import org.cpsolver.ifs.solver.Solver; 024import org.cpsolver.ifs.solver.SolverListener; 025import org.cpsolver.ifs.util.DataProperties; 026import org.cpsolver.ifs.util.JProf; 027import org.cpsolver.ifs.util.Progress; 028import org.cpsolver.studentsct.StudentSectioningModel; 029import org.cpsolver.studentsct.heuristics.studentord.StudentChoiceRealFirstOrder; 030import org.cpsolver.studentsct.heuristics.studentord.StudentOrder; 031import org.cpsolver.studentsct.model.CourseRequest; 032import org.cpsolver.studentsct.model.Enrollment; 033import org.cpsolver.studentsct.model.Request; 034import org.cpsolver.studentsct.model.Student; 035import org.cpsolver.studentsct.model.Student.StudentPriority; 036 037/** 038 * Pick a student (one by one) with an incomplete schedule, try to find an 039 * improvement, identify problematic students. <br> 040 * <br> 041 * For each request that does not have an assignment and that can be assined 042 * (see {@link Student#canAssign(Assignment, Request)}) a randomly selected sub-domain is 043 * visited. For every such enrollment, a set of conflicting enrollments is 044 * computed and a possible student that can get an alternative enrollment is 045 * identified (if there is any). For each such move a value (the cost of moving 046 * the problematic student somewhere else) is computed and the best possible 047 * move is selected at the end. If there is no such move, a set of problematic 048 * students is identified, i.e., the students whose enrollments are preventing 049 * this student to get a request. <br> 050 * <br> 051 * Each student can be selected for this swap move multiple times, but only if 052 * there is still a request that can be resolved. At the end (when there is no 053 * other neighbour), the set of all such problematic students can be returned 054 * using the {@link ProblemStudentsProvider} interface. <br> 055 * <br> 056 * Parameters: <br> 057 * <table border='1' summary='Related Solver Parameters'> 058 * <tr> 059 * <th>Parameter</th> 060 * <th>Type</th> 061 * <th>Comment</th> 062 * </tr> 063 * <tr> 064 * <td>Neighbour.SwapStudentsTimeout</td> 065 * <td>{@link Integer}</td> 066 * <td>Timeout for each neighbour selection (in milliseconds).</td> 067 * </tr> 068 * <tr> 069 * <td>Neighbour.SwapStudentsMaxValues</td> 070 * <td>{@link Integer}</td> 071 * <td>Limit for the number of considered values for each course request (see 072 * {@link CourseRequest#computeRandomEnrollments(Assignment, int)}).</td> 073 * </tr> 074 * </table> 075 * <br> 076 * <br> 077 * 078 * @version StudentSct 1.3 (Student Sectioning)<br> 079 * Copyright (C) 2007 - 2014 Tomáš Müller<br> 080 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 081 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 082 * <br> 083 * This library is free software; you can redistribute it and/or modify 084 * it under the terms of the GNU Lesser General Public License as 085 * published by the Free Software Foundation; either version 3 of the 086 * License, or (at your option) any later version. <br> 087 * <br> 088 * This library is distributed in the hope that it will be useful, but 089 * WITHOUT ANY WARRANTY; without even the implied warranty of 090 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 091 * Lesser General Public License for more details. <br> 092 * <br> 093 * You should have received a copy of the GNU Lesser General Public 094 * License along with this library; if not see 095 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 096 */ 097 098public class SwapStudentSelection implements NeighbourSelection<Request, Enrollment>, ProblemStudentsProvider, InfoProvider<Request, Enrollment>, SolverListener<Request, Enrollment> { 099 private static Logger sLog = Logger.getLogger(SwapStudentSelection.class); 100 private Set<Student> iProblemStudents = Collections.synchronizedSet(new HashSet<Student>()); 101 private LinkedList<Student> iStudents = null; 102 private static DecimalFormat sDF = new DecimalFormat("0.00"); 103 private int iTimeout = 5000; 104 private int iMaxValues = 100; 105 public static boolean sDebug = false; 106 protected StudentOrder iOrder = new StudentChoiceRealFirstOrder(); 107 private boolean iPreferPriorityStudents = true; 108 109 protected long iNbrIterations = 0; 110 protected long iTotalTime = 0; 111 protected long iNbrTimeoutReached = 0; 112 protected long iNbrNoSolution = 0; 113 114 /** 115 * Constructor 116 * 117 * @param properties 118 * configuration 119 */ 120 public SwapStudentSelection(DataProperties properties) { 121 iTimeout = properties.getPropertyInt("Neighbour.SwapStudentsTimeout", iTimeout); 122 iMaxValues = properties.getPropertyInt("Neighbour.SwapStudentsMaxValues", iMaxValues); 123 if (properties.getProperty("Neighbour.SwapStudentsOrder") != null) { 124 try { 125 iOrder = (StudentOrder) Class.forName(properties.getProperty("Neighbour.SwapStudentsOrder")) 126 .getConstructor(new Class[] { DataProperties.class }).newInstance(new Object[] { properties }); 127 } catch (Exception e) { 128 sLog.error("Unable to set student order, reason:" + e.getMessage(), e); 129 } 130 } 131 iPreferPriorityStudents = properties.getPropertyBoolean("Sectioning.PriorityStudentsFirstSelection.AllIn", true); 132 } 133 134 /** Initialization */ 135 @Override 136 public void init(Solver<Request, Enrollment> solver) { 137 List<Student> students = iOrder.order(((StudentSectioningModel) solver.currentSolution().getModel()).getStudents()); 138 iStudents = new LinkedList<Student>(students); 139 iProblemStudents.clear(); 140 Progress.getInstance(solver.currentSolution().getModel()).setPhase("Student swap...", students.size()); 141 142 iNbrIterations = 0; 143 iNbrTimeoutReached = 0; 144 iNbrNoSolution = 0; 145 iTotalTime = 0; 146 } 147 148 protected synchronized Student nextStudent() { 149 return iStudents.poll(); 150 } 151 152 public synchronized void addStudent(Student student) { 153 if (iStudents != null && student != null && !student.isDummy()) { 154 if (student.getPriority().ordinal() < StudentPriority.Normal.ordinal()) { 155 for (ListIterator<Student> i = iStudents.listIterator(); i.hasNext();) { 156 Student s = i.next(); 157 if (s.getPriority().compareTo(student.getPriority()) > 0) { 158 i.previous(); // go one back 159 i.add(student); 160 return; 161 } 162 } 163 } 164 iStudents.add(student); 165 } 166 } 167 168 /** 169 * For each student that does not have a complete schedule, try to find a 170 * request and a student that can be moved out of an enrollment so that the 171 * selected student can be assigned to the selected request. 172 */ 173 @Override 174 public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) { 175 Student student = null; 176 while ((student = nextStudent()) != null) { 177 Progress p = Progress.getInstance(solution.getModel()); 178 p.incProgress(); 179 if (p.getProgress() > 2.0 * p.getProgressMax()) return null; 180 if (student.isComplete(solution.getAssignment()) || student.nrAssignedRequests(solution.getAssignment()) == 0) 181 continue; 182 for (int i = 0; i < 5; i++) { 183 try { 184 Selection selection = getSelection(solution.getAssignment(), student); 185 Neighbour<Request, Enrollment> neighbour = selection.select(); 186 if (neighbour != null) { 187 addStudent(student); 188 return neighbour; 189 } else 190 iProblemStudents.addAll(selection.getProblemStudents()); 191 break; 192 } catch (ConcurrentModificationException e) {} 193 } 194 } 195 return null; 196 } 197 198 /** List of problematic students */ 199 @Override 200 public Set<Student> getProblemStudents() { 201 return iProblemStudents; 202 } 203 204 /** Selection subclass for a student 205 * @param assignment current assignment 206 * @param student selected student 207 * @return swap student selection 208 **/ 209 public Selection getSelection(Assignment<Request, Enrollment> assignment, Student student) { 210 return new Selection(student, assignment); 211 } 212 213 /** This class looks for a possible swap move for the given student */ 214 public class Selection { 215 private Student iStudent; 216 private long iT0, iT1; 217 private boolean iTimeoutReached; 218 private Enrollment iBestEnrollment; 219 private double iBestValue; 220 private Set<Student> iProblemStudents; 221 private List<Enrollment> iBestSwaps; 222 private Assignment<Request, Enrollment> iAssignment; 223 224 /** 225 * Constructor 226 * 227 * @param assignment current assignment 228 * @param student 229 * given student 230 */ 231 public Selection(Student student, Assignment<Request, Enrollment> assignment) { 232 iStudent = student; 233 iAssignment = assignment; 234 } 235 236 /** 237 * Check if the given conflicting enrollment can be unassigned 238 * @param conflict given enrollment 239 * @return if running MPP, do not unassign initial enrollments 240 */ 241 public boolean canUnassign(Enrollment enrollment, Enrollment conflict, Assignment<Request, Enrollment> assignment) { 242 if (conflict.getRequest().isMPP() && conflict.equals(conflict.getRequest().getInitialAssignment()) && 243 !enrollment.equals(enrollment.getRequest().getInitialAssignment())) return false; 244 if (conflict.getRequest() instanceof CourseRequest && ((CourseRequest)conflict.getRequest()).getFixedValue() != null) return false; 245 if (conflict.getRequest().getStudent().hasMinCredit()) { 246 float credit = conflict.getRequest().getStudent().getAssignedCredit(assignment) - conflict.getCredit(); 247 if (credit < conflict.getRequest().getStudent().getMinCredit()) return false; 248 } 249 if (!conflict.getRequest().isAlternative() && conflict.getRequest().getRequestPriority().isHigher(enrollment.getRequest())) return false; 250 if (iPreferPriorityStudents || conflict.getRequest().getRequestPriority().isSame(enrollment.getRequest())) { 251 if (conflict.getStudent().getPriority().isHigher(enrollment.getStudent())) return false; 252 } 253 return true; 254 } 255 256 /** 257 * The actual selection 258 * @return student swap neighbour 259 */ 260 public SwapStudentNeighbour select() { 261 if (sDebug) 262 sLog.debug("select(S" + iStudent.getId() + ")"); 263 iT0 = JProf.currentTimeMillis(); 264 iTimeoutReached = false; 265 iBestEnrollment = null; 266 iProblemStudents = new HashSet<Student>(); 267 Double initialValue = null; 268 for (Request request : iStudent.getRequests()) { 269 if (initialValue == null) 270 initialValue = request.getModel().getTotalValue(iAssignment); 271 if (iTimeout > 0 && (JProf.currentTimeMillis() - iT0) > iTimeout) { 272 if (!iTimeoutReached) { 273 if (sDebug) 274 sLog.debug(" -- timeout reached"); 275 iTimeoutReached = true; 276 } 277 break; 278 } 279 if (iAssignment.getValue(request) != null) 280 continue; 281 if (!iStudent.canAssign(iAssignment, request)) 282 continue; 283 if (sDebug) 284 sLog.debug(" -- checking request " + request); 285 List<Enrollment> values = null; 286 if (iMaxValues > 0 && request instanceof CourseRequest) { 287 values = ((CourseRequest) request).computeRandomEnrollments(iAssignment, iMaxValues); 288 } else 289 values = request.values(iAssignment); 290 values: for (Enrollment enrollment : values) { 291 if (iTimeout > 0 && (JProf.currentTimeMillis() - iT0) > iTimeout) { 292 if (!iTimeoutReached) { 293 if (sDebug) 294 sLog.debug(" -- timeout reached"); 295 iTimeoutReached = true; 296 } 297 break; 298 } 299 if (sDebug) 300 sLog.debug(" -- enrollment " + enrollment); 301 Set<Enrollment> conflicts = enrollment.variable().getModel().conflictValues(iAssignment, enrollment); 302 if (conflicts.contains(enrollment)) 303 continue; 304 305 double bound = enrollment.toDouble(iAssignment); 306 for (Enrollment conflict: conflicts) { 307 bound += conflict.variable().getBound(); 308 if (!canUnassign(enrollment, conflict, iAssignment)) continue values; 309 } 310 if (iBestEnrollment != null && bound >= iBestValue) 311 continue; 312 313 for (Enrollment conflict: conflicts) 314 iAssignment.unassign(0, conflict.variable()); 315 iAssignment.assign(0, enrollment); 316 317 boolean allResolved = true; 318 List<Enrollment> swaps = new ArrayList<Enrollment>(conflicts.size()); 319 for (Enrollment conflict : conflicts) { 320 if (sDebug) 321 sLog.debug(" -- conflict " + conflict); 322 Enrollment other = bestSwap(iAssignment, conflict, enrollment, iProblemStudents); 323 if (other == null) { 324 if (sDebug) 325 sLog.debug(" -- unable to resolve"); 326 allResolved = false; 327 break; 328 } 329 iAssignment.assign(0, other); 330 swaps.add(other); 331 if (sDebug) 332 sLog.debug(" -- can be resolved by switching to " + other.getName()); 333 } 334 double value = request.getModel().getTotalValue(iAssignment) - initialValue; 335 336 for (Enrollment other: swaps) 337 iAssignment.unassign(0, other.variable()); 338 iAssignment.unassign(0, enrollment.variable()); 339 for (Enrollment conflict: conflicts) 340 iAssignment.assign(0, conflict); 341 342 if (allResolved && value <= 0.0 && (iBestEnrollment == null || iBestValue > value)) { 343 iBestEnrollment = enrollment; 344 iBestValue = value; 345 iBestSwaps = swaps; 346 } 347 } 348 } 349 iT1 = JProf.currentTimeMillis(); 350 351 iNbrIterations ++; 352 iTotalTime += (iT1 - iT0); 353 if (iTimeoutReached) iNbrTimeoutReached ++; 354 if (iBestEnrollment == null) iNbrNoSolution ++; 355 356 if (sDebug) 357 sLog.debug(" -- done, best enrollment is " + iBestEnrollment); 358 if (iBestEnrollment == null) { 359 if (iProblemStudents.isEmpty()) 360 iProblemStudents.add(iStudent); 361 if (sDebug) 362 sLog.debug(" -- problem students are: " + iProblemStudents); 363 return null; 364 } 365 if (sDebug) 366 sLog.debug(" -- value " + iBestValue); 367 Enrollment[] assignment = new Enrollment[iStudent.getRequests().size()]; 368 int idx = 0; 369 for (Request request : iStudent.getRequests()) { 370 assignment[idx++] = (iBestEnrollment.getRequest().equals(request) ? iBestEnrollment 371 : (Enrollment) request.getAssignment(iAssignment)); 372 } 373 return new SwapStudentNeighbour(iBestValue, iBestEnrollment, iBestSwaps); 374 } 375 376 /** Was timeout reached during the selection 377 * @return was timeout reached 378 **/ 379 public boolean isTimeoutReached() { 380 return iTimeoutReached; 381 } 382 383 /** Time spent in the last selection 384 * @return search time 385 **/ 386 public long getTime() { 387 return iT1 - iT0; 388 } 389 390 /** The best enrollment found. 391 * @return best enrollment 392 **/ 393 public Enrollment getBestEnrollment() { 394 return iBestEnrollment; 395 } 396 397 /** Cost of the best enrollment found 398 * @return best value 399 **/ 400 public double getBestValue() { 401 return iBestValue; 402 } 403 404 /** Set of problematic students computed in the last selection 405 * @return identified problematic students 406 **/ 407 public Set<Student> getProblemStudents() { 408 return iProblemStudents; 409 } 410 411 } 412 413 /** 414 * Identify the best swap for the given student 415 * 416 * @param assignment current assignment 417 * @param conflict 418 * conflicting enrollment 419 * @param enrl 420 * enrollment that is visited (to be assigned to the given 421 * student) 422 * @param problematicStudents 423 * the current set of problematic students 424 * @return best alternative enrollment for the student of the conflicting 425 * enrollment 426 */ 427 public static Enrollment bestSwap(Assignment<Request, Enrollment> assignment, Enrollment conflict, Enrollment enrl, Set<Student> problematicStudents) { 428 Enrollment bestEnrollment = null; 429 double bestValue = 0; 430 for (Enrollment enrollment : conflict.getRequest().values(assignment)) { 431 if (conflict.variable().getModel().inConflict(assignment, enrollment)) 432 continue; 433 double value = enrollment.toDouble(assignment); 434 if (bestEnrollment == null || bestValue > value) { 435 bestEnrollment = enrollment; 436 bestValue = value; 437 } 438 } 439 if (bestEnrollment == null && problematicStudents != null) { 440 boolean added = false; 441 for (Enrollment enrollment : conflict.getRequest().values(assignment)) { 442 Set<Enrollment> conflicts = conflict.variable().getModel().conflictValues(assignment, enrollment); 443 for (Enrollment c : conflicts) { 444 if (enrl.getStudent().isDummy() && !c.getStudent().isDummy()) 445 continue; 446 if (enrl.getStudent().equals(c.getStudent()) || conflict.getStudent().equals(c.getStudent())) 447 continue; 448 problematicStudents.add(c.getStudent()); 449 } 450 } 451 if (!added && !enrl.getStudent().equals(conflict.getStudent())) 452 problematicStudents.add(conflict.getStudent()); 453 } 454 return bestEnrollment; 455 } 456 457 /** Neighbour that contains the swap */ 458 public static class SwapStudentNeighbour implements Neighbour<Request, Enrollment> { 459 private double iValue; 460 private Enrollment iEnrollment; 461 private List<Enrollment> iSwaps; 462 463 /** 464 * Constructor 465 * 466 * @param value 467 * cost of the move 468 * @param enrollment 469 * the enrollment which is to be assigned to the given 470 * student 471 * @param swaps 472 * enrollment swaps 473 */ 474 public SwapStudentNeighbour(double value, Enrollment enrollment, List<Enrollment> swaps) { 475 iValue = value; 476 iEnrollment = enrollment; 477 iSwaps = swaps; 478 } 479 480 @Override 481 public double value(Assignment<Request, Enrollment> assignment) { 482 return iValue; 483 } 484 485 public Student getStudent() { return iEnrollment.getStudent(); } 486 487 /** 488 * Perform the move. All the requeired swaps are identified and 489 * performed as well. 490 **/ 491 @Override 492 public void assign(Assignment<Request, Enrollment> assignment, long iteration) { 493 assignment.unassign(iteration, iEnrollment.variable()); 494 for (Enrollment swap : iSwaps) { 495 assignment.unassign(iteration, swap.variable(), swap); 496 } 497 assignment.assign(iteration, iEnrollment); 498 for (Enrollment swap : iSwaps) { 499 assignment.assign(iteration, swap); 500 } 501 } 502 503 @Override 504 public String toString() { 505 StringBuffer sb = new StringBuffer("SwSt{"); 506 sb.append(" " + iEnrollment.getRequest().getStudent()); 507 sb.append(" (" + iValue + ")"); 508 sb.append("\n " + iEnrollment.getRequest()); 509 sb.append(" " + iEnrollment); 510 for (Enrollment swap : iSwaps) { 511 sb.append("\n " + swap.getRequest()); 512 sb.append(" -> " + swap); 513 } 514 sb.append("\n}"); 515 return sb.toString(); 516 } 517 518 @Override 519 public Map<Request, Enrollment> assignments() { 520 Map<Request, Enrollment> ret = new HashMap<Request, Enrollment>(); 521 ret.put(iEnrollment.variable(), iEnrollment); 522 for (Enrollment swap : iSwaps) 523 ret.put(swap.variable(), swap); 524 return ret; 525 } 526 } 527 528 @Override 529 public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info) { 530 if (iNbrIterations > 0) 531 info.put("Timing of " + getClass().getSimpleName(), sDF.format(((double)iTotalTime) / iNbrIterations) + " ms/it (" + 532 iNbrIterations + " iterations, " + 533 (iNbrNoSolution == 0 ? "" : sDF.format(100.0 * iNbrNoSolution / iNbrIterations) + "% no solution, ") + 534 sDF.format(100.0 * iNbrTimeoutReached / iNbrIterations) + "% time limit of " + sDF.format(iTimeout / 1000.0) + " seconds reached)"); 535 } 536 537 @Override 538 public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info, Collection<Request> variables) { 539 } 540 541 @Override 542 public boolean variableSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable) { 543 return false; 544 } 545 @Override 546 public boolean valueSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable, Enrollment value) { 547 return false; 548 } 549 @Override 550 public boolean neighbourSelected(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) { 551 return false; 552 } 553 @Override 554 public void neighbourFailed(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) { 555 if (neighbour instanceof SwapStudentNeighbour) 556 addStudent(((SwapStudentNeighbour)neighbour).getStudent()); 557 } 558}