001 package net.sf.cpsolver.studentsct.heuristics.selection;
002
003 import java.text.DecimalFormat;
004 import java.util.Collections;
005 import java.util.Comparator;
006 import java.util.HashMap;
007 import java.util.HashSet;
008 import java.util.Iterator;
009 import java.util.List;
010 import java.util.Set;
011
012 import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
013 import net.sf.cpsolver.ifs.model.GlobalConstraint;
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.JProf;
019 import net.sf.cpsolver.ifs.util.Progress;
020 import net.sf.cpsolver.studentsct.StudentSectioningModel;
021 import net.sf.cpsolver.studentsct.constraint.LinkedSections;
022 import net.sf.cpsolver.studentsct.extension.DistanceConflict;
023 import net.sf.cpsolver.studentsct.extension.TimeOverlapsCounter;
024 import net.sf.cpsolver.studentsct.heuristics.studentord.StudentChoiceRealFirstOrder;
025 import net.sf.cpsolver.studentsct.heuristics.studentord.StudentOrder;
026 import net.sf.cpsolver.studentsct.model.CourseRequest;
027 import net.sf.cpsolver.studentsct.model.Enrollment;
028 import net.sf.cpsolver.studentsct.model.FreeTimeRequest;
029 import net.sf.cpsolver.studentsct.model.Request;
030 import net.sf.cpsolver.studentsct.model.Student;
031 import net.sf.cpsolver.studentsct.weights.StudentWeights;
032
033 import org.apache.log4j.Logger;
034
035 /**
036 * Section all students using incremental branch & bound (no unassignments). All
037 * students are taken in a random order, for each student a branch & bound
038 * algorithm is used to find his/her best schedule on top of all other existing
039 * student schedules (no enrollment of a different student is unassigned).
040 *
041 * <br>
042 * <br>
043 * Parameters: <br>
044 * <table border='1'>
045 * <tr>
046 * <th>Parameter</th>
047 * <th>Type</th>
048 * <th>Comment</th>
049 * </tr>
050 * <tr>
051 * <td>Neighbour.BranchAndBoundTimeout</td>
052 * <td>{@link Integer}</td>
053 * <td>Timeout for each neighbour selection (in milliseconds).</td>
054 * </tr>
055 * <tr>
056 * <td>Neighbour.BranchAndBoundMinimizePenalty</td>
057 * <td>{@link Boolean}</td>
058 * <td>If true, section penalties (instead of section values) are minimized:
059 * overall penalty is minimized together with the maximization of the number of
060 * assigned requests and minimization of distance conflicts -- this variant is
061 * to better mimic the case when students can choose their sections (section
062 * times).</td>
063 * </tr>
064 * </table>
065 * <br>
066 * <br>
067 *
068 * @version StudentSct 1.2 (Student Sectioning)<br>
069 * Copyright (C) 2007 - 2010 Tomas Muller<br>
070 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
071 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
072 * <br>
073 * This library is free software; you can redistribute it and/or modify
074 * it under the terms of the GNU Lesser General Public License as
075 * published by the Free Software Foundation; either version 3 of the
076 * License, or (at your option) any later version. <br>
077 * <br>
078 * This library is distributed in the hope that it will be useful, but
079 * WITHOUT ANY WARRANTY; without even the implied warranty of
080 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
081 * Lesser General Public License for more details. <br>
082 * <br>
083 * You should have received a copy of the GNU Lesser General Public
084 * License along with this library; if not see
085 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
086 */
087
088 public class BranchBoundSelection implements NeighbourSelection<Request, Enrollment> {
089 private static Logger sLog = Logger.getLogger(BranchBoundSelection.class);
090 private static DecimalFormat sDF = new DecimalFormat("0.00");
091 protected int iTimeout = 10000;
092 protected DistanceConflict iDistanceConflict = null;
093 protected TimeOverlapsCounter iTimeOverlaps = null;
094 protected StudentSectioningModel iModel = null;
095 public static boolean sDebug = false;
096 protected Iterator<Student> iStudentsEnumeration = null;
097 protected boolean iMinimizePenalty = false;
098 protected StudentOrder iOrder = new StudentChoiceRealFirstOrder();
099 protected double iDistConfWeight = 1.0;
100
101 /**
102 * Constructor
103 *
104 * @param properties
105 * configuration
106 */
107 public BranchBoundSelection(DataProperties properties) {
108 iTimeout = properties.getPropertyInt("Neighbour.BranchAndBoundTimeout", iTimeout);
109 iMinimizePenalty = properties.getPropertyBoolean("Neighbour.BranchAndBoundMinimizePenalty", iMinimizePenalty);
110 if (iMinimizePenalty)
111 sLog.info("Overall penalty is going to be minimized (together with the maximization of the number of assigned requests and minimization of distance conflicts).");
112 if (properties.getProperty("Neighbour.BranchAndBoundOrder") != null) {
113 try {
114 iOrder = (StudentOrder) Class.forName(properties.getProperty("Neighbour.BranchAndBoundOrder"))
115 .getConstructor(new Class[] { DataProperties.class }).newInstance(new Object[] { properties });
116 } catch (Exception e) {
117 sLog.error("Unable to set student order, reason:" + e.getMessage(), e);
118 }
119 }
120 iDistConfWeight = properties.getPropertyDouble("DistanceConflict.Weight", iDistConfWeight);
121 }
122
123 /**
124 * Initialize
125 */
126 public void init(Solver<Request, Enrollment> solver, String name) {
127 setModel((StudentSectioningModel) solver.currentSolution().getModel());
128 Progress.getInstance(solver.currentSolution().getModel()).setPhase(name, iModel.getStudents().size());
129 }
130
131 public void setModel(StudentSectioningModel model) {
132 iModel = model;
133 List<Student> students = iOrder.order(iModel.getStudents());
134 iStudentsEnumeration = students.iterator();
135 iTimeOverlaps = model.getTimeOverlaps();
136 iDistanceConflict = model.getDistanceConflict();
137 }
138
139 @Override
140 public void init(Solver<Request, Enrollment> solver) {
141 init(solver, "Branch&bound...");
142 }
143
144 /**
145 * Select neighbour. All students are taken, one by one in a random order.
146 * For each student a branch & bound search is employed.
147 */
148 @Override
149 public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) {
150 while (iStudentsEnumeration.hasNext()) {
151 Student student = iStudentsEnumeration.next();
152 Progress.getInstance(solution.getModel()).incProgress();
153 Neighbour<Request, Enrollment> neighbour = getSelection(student).select();
154 if (neighbour != null)
155 return neighbour;
156 }
157 return null;
158 }
159
160 /**
161 * Branch & bound selection for a student
162 */
163 public Selection getSelection(Student student) {
164 return new Selection(student);
165 }
166
167 /**
168 * Branch & bound selection for a student
169 */
170 public class Selection {
171 /** Student */
172 protected Student iStudent;
173 /** Start time */
174 protected long iT0;
175 /** End time */
176 protected long iT1;
177 /** Was timeout reached */
178 protected boolean iTimeoutReached;
179 /** Current assignment */
180 protected Enrollment[] iAssignment;
181 /** Best assignment */
182 protected Enrollment[] iBestAssignment;
183 /** Best value */
184 protected double iBestValue;
185 /** Value cache */
186 protected HashMap<CourseRequest, List<Enrollment>> iValues;
187
188 /**
189 * Constructor
190 *
191 * @param student
192 * selected student
193 */
194 public Selection(Student student) {
195 iStudent = student;
196 }
197
198 /**
199 * Execute branch & bound, return the best found schedule for the
200 * selected student.
201 */
202 public BranchBoundNeighbour select() {
203 iT0 = JProf.currentTimeMillis();
204 iTimeoutReached = false;
205 iAssignment = new Enrollment[iStudent.getRequests().size()];
206 iBestAssignment = null;
207 iBestValue = 0;
208
209 int i = 0;
210 for (Request r: iStudent.getRequests())
211 iAssignment[i++] = r.getAssignment();
212 saveBest();
213 for (int j = 0; j < iAssignment.length; j++)
214 iAssignment[j] = null;
215
216
217 iValues = new HashMap<CourseRequest, List<Enrollment>>();
218 backTrack(0);
219 iT1 = JProf.currentTimeMillis();
220 if (iBestAssignment == null)
221 return null;
222 return new BranchBoundNeighbour(iStudent, iBestValue, iBestAssignment);
223 }
224
225 /** Was timeout reached */
226 public boolean isTimeoutReached() {
227 return iTimeoutReached;
228 }
229
230 /** Time (in milliseconds) the branch & bound did run */
231 public long getTime() {
232 return iT1 - iT0;
233 }
234
235 /** Best schedule */
236 public Enrollment[] getBestAssignment() {
237 return iBestAssignment;
238 }
239
240 /** Value of the best schedule */
241 public double getBestValue() {
242 return iBestValue;
243 }
244
245 /** Number of requests assigned in the best schedule */
246 public int getBestNrAssigned() {
247 int nrAssigned = 0;
248 for (int i = 0; i < iBestAssignment.length; i++)
249 if (iBestAssignment[i] != null)
250 nrAssigned += (iBestAssignment[i].isCourseRequest() ? 10 : 1);
251 return nrAssigned;
252 }
253
254 /** Bound for the number of assigned requests in the current schedule */
255 public int getNrAssignedBound(int idx) {
256 int bound = 0;
257 int i = 0, alt = 0;
258 for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); i++) {
259 Request r = e.next();
260 boolean cr = r instanceof CourseRequest;
261 if (i < idx) {
262 if (iAssignment[i] != null)
263 bound += (cr ? 10 : 1);
264 if (r.isAlternative()) {
265 if (iAssignment[i] != null || (cr && ((CourseRequest) r).isWaitlist()))
266 alt--;
267 } else {
268 if (cr && !((CourseRequest) r).isWaitlist() && iAssignment[i] == null)
269 alt++;
270 }
271 } else {
272 if (!r.isAlternative())
273 bound += (cr ? 10 : 1);
274 else if (alt > 0) {
275 bound += (cr ? 10 : 1);
276 alt--;
277 }
278 }
279 }
280 return bound;
281 }
282
283 /**
284 * Distance conflicts of idx-th assignment of the current
285 * schedule
286 */
287 public Set<DistanceConflict.Conflict> getDistanceConflicts(int idx) {
288 if (iDistanceConflict == null || iAssignment[idx] == null)
289 return null;
290 Set<DistanceConflict.Conflict> dist = iDistanceConflict.conflicts(iAssignment[idx]);
291 for (int x = 0; x < idx; x++)
292 if (iAssignment[x] != null)
293 dist.addAll(iDistanceConflict.conflicts(iAssignment[x], iAssignment[idx]));
294 return dist;
295 }
296
297 /**
298 * Time overlapping conflicts of idx-th assignment of the current
299 * schedule
300 */
301 public Set<TimeOverlapsCounter.Conflict> getTimeOverlappingConflicts(int idx) {
302 if (iTimeOverlaps == null || iAssignment[idx] == null)
303 return null;
304 Set<TimeOverlapsCounter.Conflict> overlaps = new HashSet<TimeOverlapsCounter.Conflict>();
305 for (int x = 0; x < idx; x++)
306 if (iAssignment[x] != null)
307 overlaps.addAll(iTimeOverlaps.conflicts(iAssignment[x], iAssignment[idx]));
308 else if (iStudent.getRequests().get(x) instanceof FreeTimeRequest)
309 overlaps.addAll(iTimeOverlaps.conflicts(((FreeTimeRequest)iStudent.getRequests().get(x)).createEnrollment(), iAssignment[idx]));
310 return overlaps;
311 }
312
313 /**
314 * Weight of an assignment. Unlike {@link StudentWeights#getWeight(Enrollment, Set, Set)}, only count this side of distance conflicts and time overlaps.
315 **/
316 protected double getWeight(Enrollment enrollment, Set<DistanceConflict.Conflict> distanceConflicts, Set<TimeOverlapsCounter.Conflict> timeOverlappingConflicts) {
317 double weight = - iModel.getStudentWeights().getWeight(enrollment);
318 if (distanceConflicts != null)
319 for (DistanceConflict.Conflict c: distanceConflicts) {
320 Enrollment other = (c.getE1().equals(enrollment) ? c.getE2() : c.getE1());
321 if (other.getRequest().getPriority() <= enrollment.getRequest().getPriority())
322 weight += iModel.getStudentWeights().getDistanceConflictWeight(c);
323 }
324 if (timeOverlappingConflicts != null)
325 for (TimeOverlapsCounter.Conflict c: timeOverlappingConflicts) {
326 weight += iModel.getStudentWeights().getTimeOverlapConflictWeight(enrollment, c);
327 }
328 return enrollment.getRequest().getWeight() * weight;
329 }
330
331 /** Return bound of a request */
332 protected double getBound(Request r) {
333 return r.getBound();
334 }
335
336 /** Bound for the current schedule */
337 public double getBound(int idx) {
338 double bound = 0.0;
339 int i = 0, alt = 0;
340 for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); i++) {
341 Request r = e.next();
342 if (i < idx) {
343 if (iAssignment[i] != null)
344 bound += getWeight(iAssignment[i], getDistanceConflicts(i), getTimeOverlappingConflicts(i));
345 if (r.isAlternative()) {
346 if (iAssignment[i] != null || (r instanceof CourseRequest && ((CourseRequest) r).isWaitlist()))
347 alt--;
348 } else {
349 if (r instanceof CourseRequest && !((CourseRequest) r).isWaitlist() && iAssignment[i] == null)
350 alt++;
351 }
352 } else {
353 if (!r.isAlternative())
354 bound += getBound(r);
355 else if (alt > 0) {
356 bound += getBound(r);
357 alt--;
358 }
359 }
360 }
361 return bound;
362 }
363
364 /** Value of the current schedule */
365 public double getValue() {
366 double value = 0.0;
367 for (int i = 0; i < iAssignment.length; i++)
368 if (iAssignment[i] != null)
369 value += getWeight(iAssignment[i], getDistanceConflicts(i), getTimeOverlappingConflicts(i));
370 return value;
371 }
372
373 /** Assignment penalty */
374 protected double getAssignmentPenalty(int i) {
375 return iAssignment[i].getPenalty() + iDistConfWeight * getDistanceConflicts(i).size();
376 }
377
378 /** Penalty of the current schedule */
379 public double getPenalty() {
380 double bestPenalty = 0;
381 for (int i = 0; i < iAssignment.length; i++)
382 if (iAssignment[i] != null)
383 bestPenalty += getAssignmentPenalty(i);
384 return bestPenalty;
385 }
386
387 /** Penalty bound of the current schedule */
388 public double getPenaltyBound(int idx) {
389 double bound = 0.0;
390 int i = 0, alt = 0;
391 for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); i++) {
392 Request r = e.next();
393 if (i < idx) {
394 if (iAssignment[i] != null)
395 bound += getAssignmentPenalty(i);
396 if (r.isAlternative()) {
397 if (iAssignment[i] != null || (r instanceof CourseRequest && ((CourseRequest) r).isWaitlist()))
398 alt--;
399 } else {
400 if (r instanceof CourseRequest && !((CourseRequest) r).isWaitlist() && iAssignment[i] == null)
401 alt++;
402 }
403 } else {
404 if (!r.isAlternative()) {
405 if (r instanceof CourseRequest)
406 bound += ((CourseRequest) r).getMinPenalty();
407 } else if (alt > 0) {
408 if (r instanceof CourseRequest)
409 bound += ((CourseRequest) r).getMinPenalty();
410 alt--;
411 }
412 }
413 }
414 return bound;
415 }
416
417 /** Save the current schedule as the best */
418 public void saveBest() {
419 if (iBestAssignment == null)
420 iBestAssignment = new Enrollment[iAssignment.length];
421 for (int i = 0; i < iAssignment.length; i++)
422 iBestAssignment[i] = iAssignment[i];
423 if (iMinimizePenalty)
424 iBestValue = getPenalty();
425 else
426 iBestValue = getValue();
427 }
428
429 /** True if the enrollment is conflicting */
430 public boolean inConflict(final int idx, final Enrollment enrollment) {
431 for (GlobalConstraint<Request, Enrollment> constraint : enrollment.variable().getModel().globalConstraints())
432 if (constraint.inConflict(enrollment))
433 return true;
434 for (LinkedSections linkedSections: iStudent.getLinkedSections()) {
435 if (linkedSections.inConflict(enrollment, new LinkedSections.Assignment() {
436 @Override
437 public Enrollment getEnrollment(Request request, int index) {
438 return (index == idx ? enrollment : iAssignment[index]);
439 }
440 }) != null) return true;
441 }
442 for (int i = 0; i < iAssignment.length; i++)
443 if (iAssignment[i] != null && i != idx && iAssignment[i].isOverlapping(enrollment))
444 return true;
445 return false;
446 }
447
448 /** First conflicting enrollment */
449 public Enrollment firstConflict(int idx, Enrollment enrollment) {
450 Set<Enrollment> conflicts = enrollment.variable().getModel().conflictValues(enrollment);
451 if (conflicts.contains(enrollment))
452 return enrollment;
453 if (!conflicts.isEmpty()) {
454 for (Enrollment conflict : conflicts) {
455 if (!conflict.getStudent().equals(iStudent))
456 return conflict;
457 }
458 }
459 for (int i = 0; i < iAssignment.length; i++) {
460 if (iAssignment[i] == null || i == idx)
461 continue;
462 if (iAssignment[i].isOverlapping(enrollment))
463 return iAssignment[i];
464 }
465 return null;
466 }
467
468 /** True if the given request can be assigned */
469 public boolean canAssign(Request request, int idx) {
470 if (!request.isAlternative() || iAssignment[idx] != null)
471 return true;
472 int alt = 0;
473 int i = 0;
474 for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); i++) {
475 Request r = e.next();
476 if (r.equals(request))
477 continue;
478 if (r.isAlternative()) {
479 if (iAssignment[i] != null || (r instanceof CourseRequest && ((CourseRequest) r).isWaitlist()))
480 alt--;
481 } else {
482 if (r instanceof CourseRequest && !((CourseRequest) r).isWaitlist() && iAssignment[i] == null)
483 alt++;
484 }
485 }
486 return (alt > 0);
487 }
488
489 /** Number of assigned requests in the current schedule */
490 public int getNrAssigned() {
491 int assigned = 0;
492 for (int i = 0; i < iAssignment.length; i++)
493 if (iAssignment[i] != null)
494 assigned += (iAssignment[i].isCourseRequest() ? 10 : 1);
495 return assigned;
496 }
497
498 /** Returns true if the given request can be left unassigned */
499 protected boolean canLeaveUnassigned(Request request) {
500 return true;
501 }
502
503 /** Returns list of available enrollments for a course request */
504 protected List<Enrollment> values(final CourseRequest request) {
505 List<Enrollment> values = request.getAvaiableEnrollments();
506 Collections.sort(values, new Comparator<Enrollment>() {
507
508 private HashMap<Enrollment, Double> iValues = new HashMap<Enrollment, Double>();
509
510 private Double value(Enrollment e) {
511 Double value = iValues.get(e);
512 if (value == null) {
513 value = iModel.getStudentWeights().getWeight(e,
514 (iModel.getDistanceConflict() == null ? null : iModel.getDistanceConflict().conflicts(e)),
515 (iModel.getTimeOverlaps() == null ? null : iModel.getTimeOverlaps().freeTimeConflicts(e)));
516 iValues.put(e, value);
517 }
518 return value;
519 }
520
521 @Override
522 public int compare(Enrollment e1, Enrollment e2) {
523 if (e1.equals(request.getAssignment())) return -1;
524 if (e2.equals(request.getAssignment())) return 1;
525 Double v1 = value(e1), v2 = value(e2);
526 return v1.equals(v2) ? e1.compareTo(e2) : v2.compareTo(v1);
527 }
528
529 });
530 return values;
531 }
532
533 /** branch & bound search */
534 public void backTrack(int idx) {
535 if (sDebug)
536 sLog.debug("backTrack(" + getNrAssigned() + "/" + getValue() + "," + idx + ")");
537 if (iTimeout > 0 && (JProf.currentTimeMillis() - iT0) > iTimeout) {
538 if (sDebug)
539 sLog.debug(" -- timeout reached");
540 iTimeoutReached = true;
541 return;
542 }
543 if (iMinimizePenalty) {
544 if (getBestAssignment() != null
545 && (getNrAssignedBound(idx) < getBestNrAssigned() || (getNrAssignedBound(idx) == getBestNrAssigned() && getPenaltyBound(idx) >= getBestValue()))) {
546 if (sDebug)
547 sLog.debug(" -- branch number of assigned " + getNrAssignedBound(idx) + "<"
548 + getBestNrAssigned() + ", or penalty " + getPenaltyBound(idx) + ">=" + getBestValue());
549 return;
550 }
551 if (idx == iAssignment.length) {
552 if (getBestAssignment() == null
553 || (getNrAssigned() > getBestNrAssigned() || (getNrAssigned() == getBestNrAssigned() && getPenalty() < getBestValue()))) {
554 if (sDebug)
555 sLog.debug(" -- best solution found " + getNrAssigned() + "/" + getPenalty());
556 saveBest();
557 }
558 return;
559 }
560 } else {
561 if (getBestAssignment() != null && getBound(idx) >= getBestValue()) {
562 if (sDebug)
563 sLog.debug(" -- branch " + getBound(idx) + " >= " + getBestValue());
564 return;
565 }
566 if (idx == iAssignment.length) {
567 if (getBestAssignment() == null || getValue() < getBestValue()) {
568 if (sDebug)
569 sLog.debug(" -- best solution found " + getNrAssigned() + "/" + getValue());
570 saveBest();
571 }
572 return;
573 }
574 }
575
576 Request request = iStudent.getRequests().get(idx);
577 if (sDebug)
578 sLog.debug(" -- request: " + request);
579 if (!canAssign(request, idx)) {
580 if (sDebug)
581 sLog.debug(" -- cannot assign");
582 backTrack(idx + 1);
583 return;
584 }
585 List<Enrollment> values = null;
586 if (request instanceof CourseRequest) {
587 CourseRequest courseRequest = (CourseRequest) request;
588 if (!courseRequest.getSelectedChoices().isEmpty()) {
589 if (sDebug)
590 sLog.debug(" -- selection among selected enrollments");
591 values = courseRequest.getSelectedEnrollments(true);
592 if (values != null && !values.isEmpty()) {
593 boolean hasNoConflictValue = false;
594 for (Enrollment enrollment : values) {
595 if (inConflict(idx, enrollment))
596 continue;
597 hasNoConflictValue = true;
598 if (sDebug)
599 sLog.debug(" -- nonconflicting enrollment found: " + enrollment);
600 iAssignment[idx] = enrollment;
601 backTrack(idx + 1);
602 iAssignment[idx] = null;
603 }
604 if (hasNoConflictValue)
605 return;
606 }
607 }
608 values = iValues.get(courseRequest);
609 if (values == null) {
610 values = values(courseRequest);
611 iValues.put(courseRequest, values);
612 }
613 } else {
614 values = request.computeEnrollments();
615 }
616 if (sDebug) {
617 sLog.debug(" -- nrValues: " + values.size());
618 int vIdx = 1;
619 for (Enrollment enrollment : values) {
620 if (sDebug)
621 sLog.debug(" -- [" + vIdx + "]: " + enrollment);
622 }
623 }
624 boolean hasNoConflictValue = false;
625 for (Enrollment enrollment : values) {
626 if (sDebug)
627 sLog.debug(" -- enrollment: " + enrollment);
628 if (sDebug) {
629 Enrollment conflict = firstConflict(idx, enrollment);
630 if (conflict != null) {
631 sLog.debug(" -- in conflict with: " + conflict);
632 continue;
633 }
634 } else {
635 if (inConflict(idx, enrollment)) continue;
636 }
637 hasNoConflictValue = true;
638 iAssignment[idx] = enrollment;
639 backTrack(idx + 1);
640 iAssignment[idx] = null;
641 }
642 if (canLeaveUnassigned(request) && (!hasNoConflictValue || request instanceof CourseRequest))
643 backTrack(idx + 1);
644 }
645 }
646
647 /** Branch & bound neighbour -- a schedule of a student */
648 public static class BranchBoundNeighbour extends Neighbour<Request, Enrollment> {
649 private double iValue;
650 private Enrollment[] iAssignment;
651 private Student iStudent;
652
653 /**
654 * Constructor
655 *
656 * @param value
657 * value of the schedule
658 * @param assignment
659 * enrollments of student's requests
660 */
661 public BranchBoundNeighbour(Student student, double value, Enrollment[] assignment) {
662 iValue = value;
663 iAssignment = assignment;
664 iStudent = student;
665 }
666
667 @Override
668 public double value() {
669 return iValue;
670 }
671
672 /** Assignment */
673 public Enrollment[] getAssignment() {
674 return iAssignment;
675 }
676
677 /** Student */
678 public Student getStudent() {
679 return iStudent;
680 }
681
682 /** Assign the schedule */
683 @Override
684 public void assign(long iteration) {
685 for (Request r: iStudent.getRequests())
686 if (r.getAssignment() != null) r.unassign(iteration);
687 for (int i = 0; i < iAssignment.length; i++)
688 if (iAssignment[i] != null)
689 iAssignment[i].variable().assign(iteration, iAssignment[i]);
690 }
691
692 @Override
693 public String toString() {
694 StringBuffer sb = new StringBuffer("B&B{ " + iStudent + " " + sDF.format(-value() * 100.0) + "%");
695 int idx = 0;
696 for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); idx++) {
697 Request request = e.next();
698 sb.append("\n " + request);
699 Enrollment enrollment = iAssignment[idx];
700 if (enrollment == null)
701 sb.append(" -- not assigned");
702 else
703 sb.append(" -- " + enrollment);
704 }
705 sb.append("\n}");
706 return sb.toString();
707 }
708
709 }
710 }