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