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