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 return overlaps; 351 } 352 353 /** 354 * Weight of an assignment. Unlike {@link StudentWeights#getWeight(Assignment, Enrollment, Set, Set)}, only count this side of distance conflicts and time overlaps. 355 * @param enrollment an enrollment 356 * @param distanceConflicts set of distance conflicts 357 * @param timeOverlappingConflicts set of time overlapping conflicts 358 * @return value of the assignment 359 **/ 360 protected double getWeight(Enrollment enrollment, Set<DistanceConflict.Conflict> distanceConflicts, Set<TimeOverlapsCounter.Conflict> timeOverlappingConflicts) { 361 double weight = - iModel.getStudentWeights().getWeight(iCurrentAssignment, enrollment); 362 if (distanceConflicts != null) 363 for (DistanceConflict.Conflict c: distanceConflicts) { 364 Enrollment other = (c.getE1().equals(enrollment) ? c.getE2() : c.getE1()); 365 if (other.getRequest().getPriority() <= enrollment.getRequest().getPriority()) 366 weight += iModel.getStudentWeights().getDistanceConflictWeight(iCurrentAssignment, c); 367 } 368 if (timeOverlappingConflicts != null) 369 for (TimeOverlapsCounter.Conflict c: timeOverlappingConflicts) { 370 weight += iModel.getStudentWeights().getTimeOverlapConflictWeight(iCurrentAssignment, enrollment, c); 371 } 372 return enrollment.getRequest().getWeight() * weight; 373 } 374 375 /** Return bound of a request 376 * @param r a request 377 * @return bound 378 **/ 379 protected double getBound(Request r) { 380 return r.getBound(); 381 } 382 383 /** Bound for the current schedule 384 * @param idx index of the request 385 * @return current bound 386 **/ 387 public double getBound(int idx) { 388 double bound = 0.0; 389 int i = 0, alt = 0; 390 for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); i++) { 391 Request r = e.next(); 392 if (i < idx) { 393 if (iAssignment[i] != null) 394 bound += getWeight(iAssignment[i], getDistanceConflicts(i), getTimeOverlappingConflicts(i)); 395 if (r.isAlternative()) { 396 if (iAssignment[i] != null || (r instanceof CourseRequest && ((CourseRequest) r).isWaitlist())) 397 alt--; 398 } else { 399 if (r instanceof CourseRequest && !((CourseRequest) r).isWaitlist() && iAssignment[i] == null) 400 alt++; 401 } 402 } else { 403 if (!r.isAlternative()) 404 bound += getBound(r); 405 else if (alt > 0) { 406 bound += getBound(r); 407 alt--; 408 } 409 } 410 } 411 return bound; 412 } 413 414 /** Value of the current schedule 415 * @return value of the current schedule 416 **/ 417 public double getValue() { 418 double value = 0.0; 419 for (int i = 0; i < iAssignment.length; i++) 420 if (iAssignment[i] != null) 421 value += getWeight(iAssignment[i], getDistanceConflicts(i), getTimeOverlappingConflicts(i)); 422 return value; 423 } 424 425 /** Assignment penalty 426 * @param i index of the request 427 * @return assignment penalty 428 **/ 429 protected double getAssignmentPenalty(int i) { 430 return iAssignment[i].getPenalty() + iDistConfWeight * getDistanceConflicts(i).size(); 431 } 432 433 /** Penalty of the current schedule 434 * @return penalty of the current schedule 435 **/ 436 public double getPenalty() { 437 double bestPenalty = 0; 438 for (int i = 0; i < iAssignment.length; i++) 439 if (iAssignment[i] != null) 440 bestPenalty += getAssignmentPenalty(i); 441 return bestPenalty; 442 } 443 444 /** Penalty bound of the current schedule 445 * @param idx index of request 446 * @return current penalty bound 447 **/ 448 public double getPenaltyBound(int idx) { 449 double bound = 0.0; 450 int i = 0, alt = 0; 451 for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); i++) { 452 Request r = e.next(); 453 if (i < idx) { 454 if (iAssignment[i] != null) 455 bound += getAssignmentPenalty(i); 456 if (r.isAlternative()) { 457 if (iAssignment[i] != null || (r instanceof CourseRequest && ((CourseRequest) r).isWaitlist())) 458 alt--; 459 } else { 460 if (r instanceof CourseRequest && !((CourseRequest) r).isWaitlist() && iAssignment[i] == null) 461 alt++; 462 } 463 } else { 464 if (!r.isAlternative()) { 465 if (r instanceof CourseRequest) 466 bound += ((CourseRequest) r).getMinPenalty(); 467 } else if (alt > 0) { 468 if (r instanceof CourseRequest) 469 bound += ((CourseRequest) r).getMinPenalty(); 470 alt--; 471 } 472 } 473 } 474 return bound; 475 } 476 477 /** Save the current schedule as the best */ 478 public void saveBest() { 479 if (iBestAssignment == null) 480 iBestAssignment = new Enrollment[iAssignment.length]; 481 for (int i = 0; i < iAssignment.length; i++) 482 iBestAssignment[i] = iAssignment[i]; 483 if (iMinimizePenalty) 484 iBestValue = getPenalty(); 485 else 486 iBestValue = getValue(); 487 } 488 489 /** True if the enrollment is conflicting 490 * @param idx index of request 491 * @param enrollment enrollment in question 492 * @return true if there is a conflict with previous enrollments 493 **/ 494 public boolean inConflict(final int idx, final Enrollment enrollment) { 495 for (GlobalConstraint<Request, Enrollment> constraint : enrollment.variable().getModel().globalConstraints()) 496 if (constraint.inConflict(iCurrentAssignment, enrollment)) 497 return true; 498 for (LinkedSections linkedSections: iStudent.getLinkedSections()) { 499 if (linkedSections.inConflict(enrollment, new LinkedSections.EnrollmentAssignment() { 500 @Override 501 public Enrollment getEnrollment(Request request, int index) { 502 return (index == idx ? enrollment : iAssignment[index]); 503 } 504 }) != null) return true; 505 } 506 for (int i = 0; i < iAssignment.length; i++) 507 if (iAssignment[i] != null && i != idx && iAssignment[i].isOverlapping(enrollment)) 508 return true; 509 return false; 510 } 511 512 /** First conflicting enrollment 513 * @param idx index of request 514 * @param enrollment enrollment in question 515 * @return first conflicting enrollment 516 **/ 517 public Enrollment firstConflict(int idx, Enrollment enrollment) { 518 Set<Enrollment> conflicts = enrollment.variable().getModel().conflictValues(iCurrentAssignment, enrollment); 519 if (conflicts.contains(enrollment)) 520 return enrollment; 521 if (!conflicts.isEmpty()) { 522 for (Enrollment conflict : conflicts) { 523 if (!conflict.getStudent().equals(iStudent)) 524 return conflict; 525 } 526 } 527 for (int i = 0; i < iAssignment.length; i++) { 528 if (iAssignment[i] == null || i == idx) 529 continue; 530 if (iAssignment[i].isOverlapping(enrollment)) 531 return iAssignment[i]; 532 } 533 return null; 534 } 535 536 /** True if the given request can be assigned 537 * @param request given request 538 * @param idx index of request 539 * @return true if can be assigned 540 **/ 541 public boolean canAssign(Request request, int idx) { 542 if (!request.isAlternative() || iAssignment[idx] != null) 543 return true; 544 int alt = 0; 545 int i = 0; 546 for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); i++) { 547 Request r = e.next(); 548 if (r.equals(request)) 549 continue; 550 if (r.isAlternative()) { 551 if (iAssignment[i] != null || (r instanceof CourseRequest && ((CourseRequest) r).isWaitlist())) 552 alt--; 553 } else { 554 if (r instanceof CourseRequest && !((CourseRequest) r).isWaitlist() && iAssignment[i] == null) 555 alt++; 556 } 557 } 558 return (alt > 0); 559 } 560 561 /** Number of assigned requests in the current schedule 562 * @return number of assigned requests 563 **/ 564 public int getNrAssigned() { 565 int assigned = 0; 566 for (int i = 0; i < iAssignment.length; i++) 567 if (iAssignment[i] != null) 568 assigned += (iAssignment[i].isCourseRequest() ? 10 : 1); 569 return assigned; 570 } 571 572 /** Returns true if the given request can be left unassigned 573 * @param request given request 574 * @return true if can be left unassigned 575 **/ 576 protected boolean canLeaveUnassigned(Request request) { 577 return true; 578 } 579 580 /** Returns list of available enrollments for a course request 581 * @param request given request 582 * @return list of enrollments to consider 583 **/ 584 protected List<Enrollment> values(final CourseRequest request) { 585 List<Enrollment> values = request.getAvaiableEnrollments(iCurrentAssignment); 586 Collections.sort(values, new Comparator<Enrollment>() { 587 588 private HashMap<Enrollment, Double> iValues = new HashMap<Enrollment, Double>(); 589 590 private Double value(Enrollment e) { 591 Double value = iValues.get(e); 592 if (value == null) { 593 value = iModel.getStudentWeights().getWeight(iCurrentAssignment, e, 594 (iModel.getDistanceConflict() == null ? null : iModel.getDistanceConflict().conflicts(e)), 595 (iModel.getTimeOverlaps() == null ? null : iModel.getTimeOverlaps().freeTimeConflicts(e))); 596 iValues.put(e, value); 597 } 598 return value; 599 } 600 601 @Override 602 public int compare(Enrollment e1, Enrollment e2) { 603 if (e1.equals(iCurrentAssignment.getValue(request))) return -1; 604 if (e2.equals(iCurrentAssignment.getValue(request))) return 1; 605 Double v1 = value(e1), v2 = value(e2); 606 return v1.equals(v2) ? e1.compareTo(iCurrentAssignment, e2) : v2.compareTo(v1); 607 } 608 609 }); 610 return values; 611 } 612 613 /** branch & bound search 614 * @param idx index of request 615 **/ 616 public void backTrack(int idx) { 617 if (sDebug) 618 sLog.debug("backTrack(" + getNrAssigned() + "/" + getValue() + "," + idx + ")"); 619 if (iTimeout > 0 && (JProf.currentTimeMillis() - iT0) > iTimeout) { 620 if (sDebug) 621 sLog.debug(" -- timeout reached"); 622 iTimeoutReached = true; 623 return; 624 } 625 if (iMinimizePenalty) { 626 if (getBestAssignment() != null 627 && (getNrAssignedBound(idx) < getBestNrAssigned() || (getNrAssignedBound(idx) == getBestNrAssigned() && getPenaltyBound(idx) >= getBestValue()))) { 628 if (sDebug) 629 sLog.debug(" -- branch number of assigned " + getNrAssignedBound(idx) + "<" 630 + getBestNrAssigned() + ", or penalty " + getPenaltyBound(idx) + ">=" + getBestValue()); 631 return; 632 } 633 if (idx == iAssignment.length) { 634 if (getBestAssignment() == null 635 || (getNrAssigned() > getBestNrAssigned() || (getNrAssigned() == getBestNrAssigned() && getPenalty() < getBestValue()))) { 636 if (sDebug) 637 sLog.debug(" -- best solution found " + getNrAssigned() + "/" + getPenalty()); 638 saveBest(); 639 } 640 return; 641 } 642 } else { 643 if (getBestAssignment() != null && getBound(idx) >= getBestValue()) { 644 if (sDebug) 645 sLog.debug(" -- branch " + getBound(idx) + " >= " + getBestValue()); 646 return; 647 } 648 if (idx == iAssignment.length) { 649 if (getBestAssignment() == null || getValue() < getBestValue()) { 650 if (sDebug) 651 sLog.debug(" -- best solution found " + getNrAssigned() + "/" + getValue()); 652 saveBest(); 653 } 654 return; 655 } 656 } 657 658 Request request = iStudent.getRequests().get(idx); 659 if (sDebug) 660 sLog.debug(" -- request: " + request); 661 if (!canAssign(request, idx)) { 662 if (sDebug) 663 sLog.debug(" -- cannot assign"); 664 backTrack(idx + 1); 665 return; 666 } 667 List<Enrollment> values = null; 668 if (request instanceof CourseRequest) { 669 CourseRequest courseRequest = (CourseRequest) request; 670 if (courseRequest.getInitialAssignment() != null && iModel.isMPP()) { 671 Enrollment enrollment = courseRequest.getInitialAssignment(); 672 if (!inConflict(idx, enrollment)) { 673 iAssignment[idx] = enrollment; 674 backTrack(idx + 1); 675 iAssignment[idx] = null; 676 return; 677 } 678 } 679 if (!courseRequest.getSelectedChoices().isEmpty()) { 680 if (sDebug) 681 sLog.debug(" -- selection among selected enrollments"); 682 values = courseRequest.getSelectedEnrollments(iCurrentAssignment, true); 683 if (values != null && !values.isEmpty()) { 684 boolean hasNoConflictValue = false; 685 for (Enrollment enrollment : values) { 686 if (inConflict(idx, enrollment)) 687 continue; 688 hasNoConflictValue = true; 689 if (sDebug) 690 sLog.debug(" -- nonconflicting enrollment found: " + enrollment); 691 iAssignment[idx] = enrollment; 692 backTrack(idx + 1); 693 iAssignment[idx] = null; 694 } 695 if (hasNoConflictValue && iBranchWhenSelectedHasNoConflict) 696 return; 697 } 698 } 699 values = iValues.get(courseRequest); 700 if (values == null) { 701 values = values(courseRequest); 702 iValues.put(courseRequest, values); 703 } 704 } else { 705 values = request.computeEnrollments(iCurrentAssignment); 706 } 707 if (sDebug) { 708 sLog.debug(" -- nrValues: " + values.size()); 709 int vIdx = 1; 710 for (Enrollment enrollment : values) { 711 if (sDebug) 712 sLog.debug(" -- [" + vIdx + "]: " + enrollment); 713 } 714 } 715 boolean hasNoConflictValue = false; 716 for (Enrollment enrollment : values) { 717 if (sDebug) 718 sLog.debug(" -- enrollment: " + enrollment); 719 if (sDebug) { 720 Enrollment conflict = firstConflict(idx, enrollment); 721 if (conflict != null) { 722 sLog.debug(" -- in conflict with: " + conflict); 723 continue; 724 } 725 } else { 726 if (inConflict(idx, enrollment)) continue; 727 } 728 hasNoConflictValue = true; 729 iAssignment[idx] = enrollment; 730 backTrack(idx + 1); 731 iAssignment[idx] = null; 732 } 733 if (canLeaveUnassigned(request) && (!hasNoConflictValue || request instanceof CourseRequest)) 734 backTrack(idx + 1); 735 } 736 } 737 738 /** Branch & bound neighbour -- a schedule of a student */ 739 public static class BranchBoundNeighbour implements Neighbour<Request, Enrollment> { 740 private double iValue; 741 private Enrollment[] iAssignment; 742 private Student iStudent; 743 744 /** 745 * Constructor 746 * 747 * @param student selected student 748 * @param value 749 * value of the schedule 750 * @param assignment 751 * enrollments of student's requests 752 */ 753 public BranchBoundNeighbour(Student student, double value, Enrollment[] assignment) { 754 iValue = value; 755 iAssignment = assignment; 756 iStudent = student; 757 } 758 759 @Override 760 public double value(Assignment<Request, Enrollment> assignment) { 761 return iValue; 762 } 763 764 /** Assignment 765 * @return an enrollment for each request of the student 766 **/ 767 public Enrollment[] getAssignment() { 768 return iAssignment; 769 } 770 771 /** Student 772 * @return selected student 773 **/ 774 public Student getStudent() { 775 return iStudent; 776 } 777 778 /** Assign the schedule */ 779 @Override 780 public void assign(Assignment<Request, Enrollment> assignment, long iteration) { 781 for (Request r: iStudent.getRequests()) 782 assignment.unassign(iteration, r); 783 for (int i = 0; i < iAssignment.length; i++) 784 if (iAssignment[i] != null) 785 assignment.assign(iteration, iAssignment[i]); 786 } 787 788 @Override 789 public String toString() { 790 StringBuffer sb = new StringBuffer("B&B{ " + iStudent + " " + sDF.format(-iValue * 100.0) + "%"); 791 int idx = 0; 792 for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); idx++) { 793 Request request = e.next(); 794 sb.append("\n " + request); 795 Enrollment enrollment = iAssignment[idx]; 796 if (enrollment == null) 797 sb.append(" -- not assigned"); 798 else 799 sb.append(" -- " + enrollment); 800 } 801 sb.append("\n}"); 802 return sb.toString(); 803 } 804 805 @Override 806 public Map<Request, Enrollment> assignments() { 807 Map<Request, Enrollment> ret = new HashMap<Request, Enrollment>(); 808 for (int i = 0; i < iAssignment.length; i++) 809 ret.put(iStudent.getRequests().get(i), iAssignment[i]); 810 return ret; 811 } 812 813 } 814}