001 package net.sf.cpsolver.studentsct.heuristics.selection;
002
003 import java.util.ArrayList;
004 import java.util.HashSet;
005 import java.util.Iterator;
006 import java.util.List;
007 import java.util.Set;
008
009 import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
010 import net.sf.cpsolver.ifs.model.Neighbour;
011 import net.sf.cpsolver.ifs.solution.Solution;
012 import net.sf.cpsolver.ifs.solver.Solver;
013 import net.sf.cpsolver.ifs.util.DataProperties;
014 import net.sf.cpsolver.ifs.util.JProf;
015 import net.sf.cpsolver.ifs.util.Progress;
016 import net.sf.cpsolver.studentsct.StudentSectioningModel;
017 import net.sf.cpsolver.studentsct.heuristics.studentord.StudentChoiceRealFirstOrder;
018 import net.sf.cpsolver.studentsct.heuristics.studentord.StudentOrder;
019 import net.sf.cpsolver.studentsct.model.CourseRequest;
020 import net.sf.cpsolver.studentsct.model.Enrollment;
021 import net.sf.cpsolver.studentsct.model.Request;
022 import net.sf.cpsolver.studentsct.model.Student;
023
024 import 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 Tomas Muller<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
087 public 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 }