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