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