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