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