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