001 package net.sf.cpsolver.studentsct.heuristics.selection;
002
003 import java.util.Collection;
004 import java.util.Enumeration;
005 import java.util.Hashtable;
006 import java.util.Iterator;
007 import java.util.Set;
008 import java.util.Vector;
009
010 import org.apache.log4j.Logger;
011
012 import net.sf.cpsolver.ifs.extension.Extension;
013 import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
014 import net.sf.cpsolver.ifs.model.Neighbour;
015 import net.sf.cpsolver.ifs.solution.Solution;
016 import net.sf.cpsolver.ifs.solver.Solver;
017 import net.sf.cpsolver.ifs.util.DataProperties;
018 import net.sf.cpsolver.ifs.util.Progress;
019 import net.sf.cpsolver.studentsct.StudentSectioningModel;
020 import net.sf.cpsolver.studentsct.extension.DistanceConflict;
021 import net.sf.cpsolver.studentsct.heuristics.studentord.StudentChoiceRealFirstOrder;
022 import net.sf.cpsolver.studentsct.heuristics.studentord.StudentOrder;
023 import net.sf.cpsolver.studentsct.model.CourseRequest;
024 import net.sf.cpsolver.studentsct.model.Enrollment;
025 import net.sf.cpsolver.studentsct.model.Request;
026 import net.sf.cpsolver.studentsct.model.Student;
027
028 /**
029 * Section all students using incremental branch & bound (no unassignments).
030 * All students are taken in a random order, for each student a branch & bound
031 * algorithm is used to find his/her best schedule on top of all other existing
032 * student schedules (no enrollment of a different student is unassigned).
033 *
034 * <br><br>
035 * Parameters:
036 * <br>
037 * <table border='1'><tr><th>Parameter</th><th>Type</th><th>Comment</th></tr>
038 * <tr><td>Neighbour.BranchAndBoundTimeout</td><td>{@link Integer}</td><td>Timeout for each neighbour selection (in milliseconds).</td></tr>
039 * <tr><td>Neighbour.BranchAndBoundMinimizePenalty</td><td>{@link Boolean}</td><td>If true, section penalties (instead of section values) are minimized:
040 * overall penalty is minimized together with the maximization of the number of assigned requests and minimization of distance conflicts
041 * -- this variant is to better mimic the case when students can choose their sections (section times).</td></tr>
042 * </table>
043 * <br><br>
044 *
045 * @version
046 * StudentSct 1.1 (Student Sectioning)<br>
047 * Copyright (C) 2007 Tomáš Müller<br>
048 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
049 * Lazenska 391, 76314 Zlin, Czech Republic<br>
050 * <br>
051 * This library is free software; you can redistribute it and/or
052 * modify it under the terms of the GNU Lesser General Public
053 * License as published by the Free Software Foundation; either
054 * version 2.1 of the License, or (at your option) any later version.
055 * <br><br>
056 * This library is distributed in the hope that it will be useful,
057 * but WITHOUT ANY WARRANTY; without even the implied warranty of
058 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
059 * Lesser General Public License for more details.
060 * <br><br>
061 * You should have received a copy of the GNU Lesser General Public
062 * License along with this library; if not, write to the Free Software
063 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
064 */
065
066 public class BranchBoundSelection implements NeighbourSelection {
067 private static Logger sLog = Logger.getLogger(BranchBoundSelection.class);
068 protected int iTimeout = 10000;
069 protected DistanceConflict iDistanceConflict = null;
070 public static boolean sDebug = false;
071 protected Enumeration iStudentsEnumeration = null;
072 protected boolean iMinimizePenalty = false;
073 protected StudentOrder iOrder = new StudentChoiceRealFirstOrder();
074 protected double iDistConfWeight = 1.0;
075
076 /**
077 * Constructor
078 * @param properties configuration
079 */
080 public BranchBoundSelection(DataProperties properties) {
081 iTimeout = properties.getPropertyInt("Neighbour.BranchAndBoundTimeout", iTimeout);
082 iMinimizePenalty = properties.getPropertyBoolean("Neighbour.BranchAndBoundMinimizePenalty", iMinimizePenalty);
083 if (iMinimizePenalty) sLog.info("Overall penalty is going to be minimized (together with the maximization of the number of assigned requests and minimization of distance conflicts).");
084 if (properties.getProperty("Neighbour.BranchAndBoundOrder")!=null) {
085 try {
086 iOrder = (StudentOrder)Class.forName(properties.getProperty("Neighbour.BranchAndBoundOrder")).
087 getConstructor(new Class[] {DataProperties.class}).
088 newInstance(new Object[] {properties});
089 } catch (Exception e) {
090 sLog.error("Unable to set student order, reason:"+e.getMessage(),e);
091 }
092 }
093 iDistConfWeight = properties.getPropertyDouble("DistanceConflict.Weight", iDistConfWeight);
094 }
095
096 /**
097 * Initialize
098 */
099 public void init(Solver solver, String name) {
100 Vector students = iOrder.order(((StudentSectioningModel)solver.currentSolution().getModel()).getStudents());
101 iStudentsEnumeration = students.elements();
102 if (iDistanceConflict==null)
103 for (Enumeration e=solver.getExtensions().elements();e.hasMoreElements();) {
104 Extension ext = (Extension)e.nextElement();
105 if (ext instanceof DistanceConflict)
106 iDistanceConflict = (DistanceConflict)ext;
107 }
108 Progress.getInstance(solver.currentSolution().getModel()).setPhase(name, students.size());
109 }
110
111 public void init(Solver solver) {
112 init(solver, "Branch&bound...");
113 }
114
115 /**
116 * Select neighbour. All students are taken, one by one in a random order.
117 * For each student a branch & bound search is employed.
118 */
119 public Neighbour selectNeighbour(Solution solution) {
120 while (iStudentsEnumeration.hasMoreElements()) {
121 Student student = (Student)iStudentsEnumeration.nextElement();
122 Progress.getInstance(solution.getModel()).incProgress();
123 Neighbour neighbour = getSelection(student).select();
124 if (neighbour!=null) return neighbour;
125 }
126 return null;
127 }
128
129 /**
130 * Branch & bound selection for a student
131 */
132 public Selection getSelection(Student student) {
133 return new Selection(student);
134 }
135
136 /**
137 * Branch & bound selection for a student
138 */
139 public class Selection {
140 /** Student */
141 protected Student iStudent;
142 /** Start time */
143 protected long iT0;
144 /** End time */
145 protected long iT1;
146 /** Was timeout reached */
147 protected boolean iTimeoutReached;
148 /** Current assignment */
149 protected Enrollment[] iAssignment;
150 /** Best assignment */
151 protected Enrollment[] iBestAssignment;
152 /** Best value */
153 protected double iBestValue;
154 /** Value cache */
155 protected Hashtable iValues;
156
157 /**
158 * Constructor
159 * @param student selected student
160 */
161 public Selection(Student student) {
162 iStudent = student;
163 }
164
165 /**
166 * Execute branch & bound, return the best found schedule for the selected student.
167 */
168 public BranchBoundNeighbour select() {
169 iT0 = System.currentTimeMillis();
170 iTimeoutReached = false;
171 iAssignment = new Enrollment[iStudent.getRequests().size()];
172 iBestAssignment = null;
173 iBestValue = 0;
174 iValues = new Hashtable();
175 backTrack(0);
176 iT1 = System.currentTimeMillis();
177 if (iBestAssignment==null) return null;
178 return new BranchBoundNeighbour(iBestValue, iBestAssignment);
179 }
180
181 /** Was timeout reached */
182 public boolean isTimeoutReached() {
183 return iTimeoutReached;
184 }
185
186 /** Time (in milliseconds) the branch & bound did run */
187 public long getTime() {
188 return iT1 - iT0;
189 }
190
191 /** Best schedule */
192 public Enrollment[] getBestAssignment() {
193 return iBestAssignment;
194 }
195
196 /** Value of the best schedule */
197 public double getBestValue() {
198 return iBestValue;
199 }
200
201 /** Number of requests assigned in the best schedule */
202 public int getBestNrAssigned() {
203 int nrAssigned = 0;
204 for (int i=0;i<iBestAssignment.length;i++)
205 if (iBestAssignment[i]!=null) nrAssigned++;
206 return nrAssigned;
207 }
208
209 /** Bound for the number of assigned requests in the current schedule */
210 public int getNrAssignedBound(int idx) {
211 int bound = 0;
212 int i=0, alt=0;
213 for (Enumeration e=iStudent.getRequests().elements();e.hasMoreElements();i++) {
214 Request r = (Request)e.nextElement();
215 if (i<idx) {
216 if (iAssignment[i]!=null)
217 bound++;
218 if (r.isAlternative()) {
219 if (iAssignment[i]!=null || (r instanceof CourseRequest && ((CourseRequest)r).isWaitlist())) alt--;
220 } else {
221 if (r instanceof CourseRequest && !((CourseRequest)r).isWaitlist() && iAssignment[i]==null) alt++;
222 }
223 } else {
224 if (!r.isAlternative())
225 bound ++;
226 else if (alt>0) {
227 bound ++; alt--;
228 }
229 }
230 }
231 return bound;
232 }
233
234 /** Number of distance conflicts of idx-th assignment of the current schedule */
235 public double getNrDistanceConflicts(int idx) {
236 if (iDistanceConflict==null || iAssignment[idx]==null) return 0;
237 double nrDist = iDistanceConflict.nrConflicts(iAssignment[idx]);
238 for (int x=0;x<idx;x++)
239 if (iAssignment[x]!=null)
240 nrDist+=iDistanceConflict.nrConflicts(iAssignment[x],iAssignment[idx]);
241 return nrDist;
242 }
243
244 /** Bound for the current schedule */
245 public double getBound(int idx) {
246 double bound = 0.0;
247 int i=0, alt=0;
248 for (Enumeration e=iStudent.getRequests().elements();e.hasMoreElements();i++) {
249 Request r = (Request)e.nextElement();
250 if (i<idx) {
251 if (iAssignment[i]!=null)
252 bound += iAssignment[i].toDouble(getNrDistanceConflicts(i));
253 if (r.isAlternative()) {
254 if (iAssignment[i]!=null || (r instanceof CourseRequest && ((CourseRequest)r).isWaitlist())) alt--;
255 } else {
256 if (r instanceof CourseRequest && !((CourseRequest)r).isWaitlist() && iAssignment[i]==null) alt++;
257 }
258 } else {
259 if (!r.isAlternative())
260 bound += r.getBound();
261 else if (alt>0) {
262 bound += r.getBound(); alt--;
263 }
264 }
265 }
266 return bound;
267 }
268
269 /** Value of the current schedule */
270 public double getValue() {
271 double value = 0.0;
272 for (int i=0;i<iAssignment.length;i++)
273 if (iAssignment[i]!=null)
274 value += iAssignment[i].toDouble(getNrDistanceConflicts(i));
275 return value;
276 }
277
278 /** Assignment penalty */
279 protected double getAssignmentPenalty(int i) {
280 return iAssignment[i].getPenalty() + iDistConfWeight*getNrDistanceConflicts(i);
281 }
282
283 /** Penalty of the current schedule */
284 public double getPenalty() {
285 double bestPenalty = 0;
286 for (int i=0;i<iAssignment.length;i++)
287 if (iAssignment[i]!=null) bestPenalty += getAssignmentPenalty(i);
288 return bestPenalty;
289 }
290
291
292 /** Penalty bound of the current schedule */
293 public double getPenaltyBound(int idx) {
294 double bound = 0.0;
295 int i=0, alt=0;
296 for (Enumeration e=iStudent.getRequests().elements();e.hasMoreElements();i++) {
297 Request r = (Request)e.nextElement();
298 if (i<idx) {
299 if (iAssignment[i]!=null)
300 bound += getAssignmentPenalty(i);
301 if (r.isAlternative()) {
302 if (iAssignment[i]!=null || (r instanceof CourseRequest && ((CourseRequest)r).isWaitlist())) alt--;
303 } else {
304 if (r instanceof CourseRequest && !((CourseRequest)r).isWaitlist() && iAssignment[i]==null) alt++;
305 }
306 } else {
307 if (!r.isAlternative()) {
308 if (r instanceof CourseRequest)
309 bound += ((CourseRequest)r).getMinPenalty();
310 } else if (alt>0) {
311 if (r instanceof CourseRequest)
312 bound += ((CourseRequest)r).getMinPenalty();
313 alt--;
314 }
315 }
316 }
317 return bound;
318 }
319
320 /** Save the current schedule as the best */
321 public void saveBest() {
322 if (iBestAssignment==null)
323 iBestAssignment = new Enrollment[iAssignment.length];
324 for (int i=0;i<iAssignment.length;i++)
325 iBestAssignment[i] = iAssignment[i];
326 if (iMinimizePenalty)
327 iBestValue = getPenalty();
328 else
329 iBestValue = getValue();
330 }
331
332 /** First conflicting enrollment */
333 public Enrollment firstConflict(int idx, Enrollment enrollment) {
334 Set conflicts = enrollment.variable().getModel().conflictValues(enrollment);
335 if (conflicts.contains(enrollment)) return enrollment;
336 if (conflicts!=null && !conflicts.isEmpty()) {
337 for (Iterator i=conflicts.iterator();i.hasNext();) {
338 Enrollment conflict = (Enrollment)i.next();
339 if (!conflict.getStudent().equals(iStudent)) return conflict;
340 }
341 }
342 for (int i=0;i<iAssignment.length;i++) {
343 if (iAssignment[i]==null) continue;
344 if (!iAssignment[i].isConsistent(enrollment)) return iAssignment[i];
345 }
346 return null;
347 }
348
349 /** True if the given request can be assigned */
350 public boolean canAssign(Request request, int idx) {
351 if (!request.isAlternative() || iAssignment[idx]!=null) return true;
352 int alt = 0;
353 int i = 0;
354 for (Enumeration e=iStudent.getRequests().elements();e.hasMoreElements();i++) {
355 Request r = (Request)e.nextElement();
356 if (r.equals(request)) continue;
357 if (r.isAlternative()) {
358 if (iAssignment[i]!=null || (r instanceof CourseRequest && ((CourseRequest)r).isWaitlist())) alt--;
359 } else {
360 if (r instanceof CourseRequest && !((CourseRequest)r).isWaitlist() && iAssignment[i]==null) alt++;
361 }
362 }
363 return (alt>0);
364 }
365
366 /** Number of assigned requests in the current schedule */
367 public int getNrAssigned() {
368 int assigned = 0;
369 for (int i=0;i<iAssignment.length;i++)
370 if (iAssignment[i]!=null) assigned++;
371 return assigned;
372 }
373
374 /** branch & bound search */
375 public void backTrack(int idx) {
376 if (sDebug) sLog.debug("backTrack("+getNrAssigned()+"/"+getValue()+","+idx+")");
377 if (iTimeout>0 && (System.currentTimeMillis()-iT0)>iTimeout) {
378 if (sDebug) sLog.debug(" -- timeout reached");
379 iTimeoutReached=true; return;
380 }
381 if (iMinimizePenalty) {
382 if (iBestAssignment!=null && (getNrAssignedBound(idx)<getBestNrAssigned() || (getNrAssignedBound(idx)==getBestNrAssigned() && getPenaltyBound(idx)>=iBestValue))) {
383 if (sDebug) sLog.debug(" -- branch number of assigned "+getNrAssignedBound(idx)+"<"+getBestNrAssigned()+", or penalty "+getPenaltyBound(idx)+">="+iBestValue);
384 return;
385 }
386 if (idx==iAssignment.length) {
387 if (iBestAssignment==null || (getNrAssigned()>getBestNrAssigned() || (getNrAssigned()==getBestNrAssigned() && getPenalty()<iBestValue))) {
388 if (sDebug) sLog.debug(" -- best solution found "+getNrAssigned()+"/"+getPenalty());
389 saveBest();
390 }
391 return;
392 }
393 } else {
394 if (iBestAssignment!=null && getBound(idx)>=iBestValue) {
395 if (sDebug) sLog.debug(" -- branch "+getBound(idx)+" >= "+iBestValue);
396 return;
397 }
398 if (idx==iAssignment.length) {
399 if (iBestAssignment==null || getValue()<iBestValue) {
400 if (sDebug) sLog.debug(" -- best solution found "+getNrAssigned()+"/"+getValue());
401 saveBest();
402 }
403 return;
404 }
405 }
406
407 Request request = (Request)iStudent.getRequests().elementAt(idx);
408 if (sDebug) sLog.debug(" -- request: "+request);
409 if (!canAssign(request, idx)) {
410 if (sDebug) sLog.debug(" -- cannot assign");
411 backTrack(idx+1);
412 return;
413 }
414 Collection values = null;
415 if (request instanceof CourseRequest) {
416 CourseRequest courseRequest = (CourseRequest)request;
417 if (!courseRequest.getSelectedChoices().isEmpty()) {
418 if (sDebug) sLog.debug(" -- selection among selected enrollments");
419 values = courseRequest.getSelectedEnrollments(true);
420 if (values!=null && !values.isEmpty()) {
421 boolean hasNoConflictValue = false;
422 for (Iterator i=values.iterator();i.hasNext();) {
423 Enrollment enrollment = (Enrollment)i.next();
424 if (firstConflict(idx, enrollment)!=null) continue;
425 hasNoConflictValue = true;
426 if (sDebug) sLog.debug(" -- nonconflicting enrollment found: "+enrollment);
427 iAssignment[idx] = enrollment;
428 backTrack(idx+1);
429 iAssignment[idx] = null;
430 }
431 if (hasNoConflictValue) return;
432 }
433 }
434 values = (Collection)iValues.get(courseRequest);
435 if (values==null) {
436 values = courseRequest.getAvaiableEnrollments();
437 iValues.put(courseRequest, values);
438 }
439 } else {
440 values = request.computeEnrollments();
441 }
442 if (sDebug) {
443 sLog.debug(" -- nrValues: "+values.size());
444 int vIdx=1;
445 for (Iterator i=values.iterator();i.hasNext();vIdx++) {
446 Enrollment enrollment = (Enrollment)i.next();
447 if (sDebug) sLog.debug(" -- ["+vIdx+"]: "+enrollment);
448 }
449 }
450 boolean hasNoConflictValue = false;
451 for (Iterator i=values.iterator();i.hasNext();) {
452 Enrollment enrollment = (Enrollment)i.next();
453 if (sDebug) sLog.debug(" -- enrollment: "+enrollment);
454 Enrollment conflict = firstConflict(idx, enrollment);
455 if (conflict!=null) {
456 if (sDebug) sLog.debug(" -- in conflict with: "+conflict);
457 continue;
458 }
459 hasNoConflictValue = true;
460 iAssignment[idx] = enrollment;
461 backTrack(idx+1);
462 iAssignment[idx] = null;
463 }
464 if (!hasNoConflictValue || request instanceof CourseRequest) backTrack(idx+1);
465 }
466 }
467
468 /** Branch & bound neighbour -- a schedule of a student */
469 public static class BranchBoundNeighbour extends Neighbour {
470 private double iValue;
471 private Enrollment[] iAssignment;
472
473 /**
474 * Constructor
475 * @param value value of the schedule
476 * @param assignment enrollments of student's requests
477 */
478 public BranchBoundNeighbour(double value, Enrollment[] assignment) {
479 iValue = value;
480 iAssignment = assignment;
481 }
482
483 public double value() {
484 return iValue;
485 }
486
487 /** Assignment */
488 public Enrollment[] getAssignment() {
489 return iAssignment;
490 }
491
492 /** Assign the schedule */
493 public void assign(long iteration) {
494 for (int i=0;i<iAssignment.length;i++)
495 if (iAssignment[i]!=null)
496 iAssignment[i].variable().assign(iteration, iAssignment[i]);
497 }
498
499 public String toString() {
500 StringBuffer sb = new StringBuffer("B&B{");
501 Student student = null;
502 for (int i=0;i<iAssignment.length;i++) {
503 if (iAssignment[i]!=null) {
504 student = iAssignment[i].getRequest().getStudent();
505 sb.append(" "+student);
506 sb.append(" ("+iValue+")");
507 break;
508 }
509 }
510 if (student!=null) {
511 int idx=0;
512 for (Enumeration e=student.getRequests().elements();e.hasMoreElements();idx++) {
513 Request request = (Request)e.nextElement();
514 sb.append("\n"+request);
515 Enrollment enrollment = iAssignment[idx];
516 if (enrollment==null)
517 sb.append(" -- not assigned");
518 else
519 sb.append(" -- "+enrollment);
520 }
521 }
522 sb.append("\n}");
523 return sb.toString();
524 }
525
526 }
527 }