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