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