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