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