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