001package net.sf.cpsolver.studentsct.heuristics.selection; 002 003import java.text.DecimalFormat; 004import java.util.Collections; 005import java.util.Comparator; 006import java.util.HashMap; 007import java.util.HashSet; 008import java.util.Iterator; 009import java.util.List; 010import java.util.Set; 011 012import net.sf.cpsolver.ifs.heuristics.NeighbourSelection; 013import net.sf.cpsolver.ifs.model.GlobalConstraint; 014import net.sf.cpsolver.ifs.model.Neighbour; 015import net.sf.cpsolver.ifs.solution.Solution; 016import net.sf.cpsolver.ifs.solver.Solver; 017import net.sf.cpsolver.ifs.util.DataProperties; 018import net.sf.cpsolver.ifs.util.JProf; 019import net.sf.cpsolver.ifs.util.Progress; 020import net.sf.cpsolver.studentsct.StudentSectioningModel; 021import net.sf.cpsolver.studentsct.constraint.LinkedSections; 022import net.sf.cpsolver.studentsct.extension.DistanceConflict; 023import net.sf.cpsolver.studentsct.extension.TimeOverlapsCounter; 024import net.sf.cpsolver.studentsct.heuristics.studentord.StudentChoiceRealFirstOrder; 025import net.sf.cpsolver.studentsct.heuristics.studentord.StudentOrder; 026import net.sf.cpsolver.studentsct.model.CourseRequest; 027import net.sf.cpsolver.studentsct.model.Enrollment; 028import net.sf.cpsolver.studentsct.model.FreeTimeRequest; 029import net.sf.cpsolver.studentsct.model.Request; 030import net.sf.cpsolver.studentsct.model.Student; 031import net.sf.cpsolver.studentsct.weights.StudentWeights; 032 033import 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 Tomáš Müller<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 088public 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}