001package org.cpsolver.studentsct.online.selection; 002 003import java.util.ArrayList; 004import java.util.Collections; 005import java.util.Comparator; 006import java.util.HashMap; 007import java.util.Hashtable; 008import java.util.Iterator; 009import java.util.List; 010import java.util.Map; 011import java.util.Set; 012 013import org.cpsolver.ifs.assignment.Assignment; 014import org.cpsolver.ifs.model.GlobalConstraint; 015import org.cpsolver.ifs.util.DataProperties; 016import org.cpsolver.ifs.util.JProf; 017import org.cpsolver.studentsct.constraint.LinkedSections; 018import org.cpsolver.studentsct.heuristics.selection.OnlineSelection; 019import org.cpsolver.studentsct.heuristics.selection.BranchBoundSelection.BranchBoundNeighbour; 020import org.cpsolver.studentsct.model.Config; 021import org.cpsolver.studentsct.model.CourseRequest; 022import org.cpsolver.studentsct.model.Enrollment; 023import org.cpsolver.studentsct.model.FreeTimeRequest; 024import org.cpsolver.studentsct.model.Request; 025import org.cpsolver.studentsct.model.Section; 026import org.cpsolver.studentsct.model.Student; 027import org.cpsolver.studentsct.model.Subpart; 028import org.cpsolver.studentsct.online.OnlineSectioningModel; 029 030/** 031 * Online student sectioning algorithm using multi-criteria selection. It is very 032 * similar to the {@link SuggestionSelection}, however, the {link {@link OnlineSelection} 033 * is used to compare two solutions and for branching. 034 * 035 * @version StudentSct 1.3 (Student Sectioning)<br> 036 * Copyright (C) 2014 Tomas Muller<br> 037 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 038 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 039 * <br> 040 * This library is free software; you can redistribute it and/or modify 041 * it under the terms of the GNU Lesser General Public License as 042 * published by the Free Software Foundation; either version 3 of the 043 * License, or (at your option) any later version. <br> 044 * <br> 045 * This library is distributed in the hope that it will be useful, but 046 * WITHOUT ANY WARRANTY; without even the implied warranty of 047 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 048 * Lesser General Public License for more details. <br> 049 * <br> 050 * You should have received a copy of the GNU Lesser General Public 051 * License along with this library; if not see <a 052 * href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>. 053 * 054 */ 055public class MultiCriteriaBranchAndBoundSelection implements OnlineSectioningSelection { 056 protected int iTimeout = 1000; 057 protected OnlineSectioningModel iModel = null; 058 protected Assignment<Request, Enrollment> iAssignment = null; 059 protected SelectionCriterion iComparator = null; 060 private boolean iPriorityWeighting = true; 061 protected boolean iBranchWhenSelectedHasNoConflict = false; 062 private double iMaxOverExpected = -1.0; 063 064 /** Student */ 065 protected Student iStudent; 066 /** Start time */ 067 protected long iT0; 068 /** End time */ 069 protected long iT1; 070 /** Was timeout reached */ 071 protected boolean iTimeoutReached; 072 /** Current assignment */ 073 protected Enrollment[] iCurrentAssignment; 074 /** Best assignment */ 075 protected Enrollment[] iBestAssignment; 076 /** Value cache */ 077 protected HashMap<CourseRequest, List<Enrollment>> iValues; 078 079 private Set<FreeTimeRequest> iRequiredFreeTimes; 080 private Hashtable<CourseRequest, Set<Section>> iPreferredSections; 081 private Hashtable<CourseRequest, Config> iRequiredConfig = new Hashtable<CourseRequest, Config>(); 082 private Hashtable<CourseRequest, Hashtable<Subpart, Section>> iRequiredSection = new Hashtable<CourseRequest, Hashtable<Subpart, Section>>(); 083 private Set<CourseRequest> iRequiredUnassinged = null; 084 085 public MultiCriteriaBranchAndBoundSelection(DataProperties config) { 086 iTimeout = config.getPropertyInt("Neighbour.BranchAndBoundTimeout", iTimeout); 087 iPriorityWeighting = config.getPropertyBoolean("StudentWeights.PriorityWeighting", iPriorityWeighting); 088 iBranchWhenSelectedHasNoConflict = config.getPropertyBoolean("Students.BranchWhenSelectedHasNoConflict", iBranchWhenSelectedHasNoConflict); 089 } 090 091 @Override 092 public void setModel(OnlineSectioningModel model) { 093 iModel = model; 094 } 095 096 @Override 097 public void setPreferredSections(Hashtable<CourseRequest, Set<Section>> preferredSections) { 098 iPreferredSections = preferredSections; 099 } 100 101 public void setTimeout(int timeout) { 102 iTimeout = timeout; 103 } 104 105 @Override 106 public void setRequiredSections(Hashtable<CourseRequest, Set<Section>> requiredSections) { 107 if (requiredSections != null) { 108 for (Map.Entry<CourseRequest, Set<Section>> entry : requiredSections.entrySet()) { 109 Hashtable<Subpart, Section> subSection = new Hashtable<Subpart, Section>(); 110 iRequiredSection.put(entry.getKey(), subSection); 111 for (Section section : entry.getValue()) { 112 if (subSection.isEmpty()) 113 iRequiredConfig.put(entry.getKey(), section.getSubpart().getConfig()); 114 subSection.put(section.getSubpart(), section); 115 } 116 } 117 } 118 } 119 120 @Override 121 public void setRequiredFreeTimes(Set<FreeTimeRequest> requiredFreeTimes) { 122 iRequiredFreeTimes = requiredFreeTimes; 123 } 124 125 public BranchBoundNeighbour select(Assignment<Request, Enrollment> assignment, Student student, 126 SelectionCriterion comparator) { 127 iStudent = student; 128 iComparator = comparator; 129 iAssignment = assignment; 130 return select(); 131 } 132 133 @Override 134 public BranchBoundNeighbour select(Assignment<Request, Enrollment> assignment, Student student) { 135 SelectionCriterion comparator = null; 136 if (iPriorityWeighting) 137 comparator = new OnlineSectioningCriterion(student, iModel, assignment, iPreferredSections); 138 else 139 comparator = new EqualWeightCriterion(student, iModel, assignment, iPreferredSections); 140 return select(assignment, student, comparator); 141 } 142 143 /** 144 * Execute branch & bound, return the best found schedule for the selected 145 * student. 146 */ 147 public BranchBoundNeighbour select() { 148 iT0 = JProf.currentTimeMillis(); 149 iTimeoutReached = false; 150 iCurrentAssignment = new Enrollment[iStudent.getRequests().size()]; 151 iBestAssignment = null; 152 153 int i = 0; 154 for (Request r : iStudent.getRequests()) 155 iCurrentAssignment[i++] = iAssignment.getValue(r); 156 saveBest(); 157 for (int j = 0; j < iCurrentAssignment.length; j++) 158 iCurrentAssignment[j] = null; 159 160 iValues = new HashMap<CourseRequest, List<Enrollment>>(); 161 backTrack(0); 162 iT1 = JProf.currentTimeMillis(); 163 if (iBestAssignment == null) 164 return null; 165 166 return new BranchBoundNeighbour(iStudent, iComparator.getTotalWeight(iAssignment, iBestAssignment), 167 iBestAssignment); 168 } 169 170 /** Was timeout reached */ 171 public boolean isTimeoutReached() { 172 return iTimeoutReached; 173 } 174 175 /** Time (in milliseconds) the branch & bound did run */ 176 public long getTime() { 177 return iT1 - iT0; 178 } 179 180 /** Save the current schedule as the best */ 181 public void saveBest() { 182 if (iBestAssignment == null) 183 iBestAssignment = new Enrollment[iCurrentAssignment.length]; 184 for (int i = 0; i < iCurrentAssignment.length; i++) 185 iBestAssignment[i] = iCurrentAssignment[i]; 186 } 187 188 /** True if the enrollment is conflicting */ 189 public boolean inConflict(final int idx, final Enrollment enrollment) { 190 for (GlobalConstraint<Request, Enrollment> constraint : enrollment.variable().getModel().globalConstraints()) 191 if (constraint.inConflict(iAssignment, enrollment)) 192 return true; 193 for (LinkedSections linkedSections : iStudent.getLinkedSections()) { 194 if (linkedSections.inConflict(enrollment, new LinkedSections.EnrollmentAssignment() { 195 @Override 196 public Enrollment getEnrollment(Request request, int index) { 197 return (index == idx ? enrollment : iCurrentAssignment[index]); 198 } 199 }) != null) 200 return true; 201 } 202 for (int i = 0; i < iCurrentAssignment.length; i++) 203 if (iCurrentAssignment[i] != null && i != idx && iCurrentAssignment[i].isOverlapping(enrollment)) 204 return true; 205 if (iMaxOverExpected >= 0.0) { 206 double penalty = 0.0; 207 for (int i = 0; i < idx; i++) { 208 if (iCurrentAssignment[i] != null && iCurrentAssignment[i].getAssignments() != null && iCurrentAssignment[i].isCourseRequest()) 209 for (Section section: iCurrentAssignment[i].getSections()) 210 penalty += iModel.getOverExpected(iAssignment, iCurrentAssignment, i, section, iCurrentAssignment[i].getRequest()); 211 } 212 if (enrollment.isCourseRequest()) 213 for (Section section: enrollment.getSections()) 214 penalty += iModel.getOverExpected(iAssignment, iCurrentAssignment, idx, section, enrollment.getRequest()); 215 if (penalty > iMaxOverExpected) return true; 216 } 217 return !isAllowed(idx, enrollment); 218 } 219 220 /** True if the given request can be assigned */ 221 public boolean canAssign(Request request, int idx) { 222 if (!request.isAlternative() || iCurrentAssignment[idx] != null) 223 return true; 224 int alt = 0; 225 int i = 0; 226 for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); i++) { 227 Request r = e.next(); 228 if (r.equals(request)) 229 continue; 230 if (r.isAlternative()) { 231 if (iCurrentAssignment[i] != null || (r instanceof CourseRequest && ((CourseRequest) r).isWaitlist())) 232 alt--; 233 } else { 234 if (r instanceof CourseRequest && !((CourseRequest) r).isWaitlist() && iCurrentAssignment[i] == null) 235 alt++; 236 } 237 } 238 return (alt > 0); 239 } 240 241 public boolean isAllowed(int idx, Enrollment enrollment) { 242 if (enrollment.isCourseRequest()) { 243 CourseRequest request = (CourseRequest) enrollment.getRequest(); 244 if (iRequiredUnassinged != null && iRequiredUnassinged.contains(request)) return false; 245 Config reqConfig = iRequiredConfig.get(request); 246 if (reqConfig != null) { 247 if (!reqConfig.equals(enrollment.getConfig())) 248 return false; 249 Hashtable<Subpart, Section> reqSections = iRequiredSection.get(request); 250 for (Section section : enrollment.getSections()) { 251 Section reqSection = reqSections.get(section.getSubpart()); 252 if (reqSection == null) 253 continue; 254 if (!section.equals(reqSection)) 255 return false; 256 } 257 } 258 } else if (iRequiredFreeTimes.contains(enrollment.getRequest())) { 259 if (enrollment.getAssignments() == null || enrollment.getAssignments().isEmpty()) 260 return false; 261 } 262 return true; 263 } 264 265 /** Returns true if the given request can be left unassigned */ 266 protected boolean canLeaveUnassigned(Request request) { 267 if (request instanceof CourseRequest) { 268 if (iRequiredConfig.get(request) != null) 269 return false; 270 } else if (iRequiredFreeTimes.contains(request)) 271 return false; 272 return true; 273 } 274 275 /** Returns list of available enrollments for a course request */ 276 protected List<Enrollment> values(final CourseRequest request) { 277 if (iRequiredUnassinged != null && iRequiredUnassinged.contains(request)) 278 return new ArrayList<Enrollment>(); 279 List<Enrollment> values = request.getAvaiableEnrollments(iAssignment); 280 Collections.sort(values, new Comparator<Enrollment>() { 281 @Override 282 public int compare(Enrollment o1, Enrollment o2) { 283 return iComparator.compare(iAssignment, o1, o2); 284 } 285 }); 286 return values; 287 } 288 289 /** branch & bound search */ 290 public void backTrack(int idx) { 291 if (iTimeout > 0 && (JProf.currentTimeMillis() - iT0) > iTimeout) { 292 iTimeoutReached = true; 293 return; 294 } 295 if (idx == iCurrentAssignment.length) { 296 if (iBestAssignment == null || iComparator.compare(iAssignment, iCurrentAssignment, iBestAssignment) < 0) 297 saveBest(); 298 return; 299 } else if (iBestAssignment != null 300 && !iComparator.canImprove(iAssignment, idx, iCurrentAssignment, iBestAssignment)) { 301 return; 302 } 303 304 Request request = iStudent.getRequests().get(idx); 305 if (!canAssign(request, idx)) { 306 backTrack(idx + 1); 307 return; 308 } 309 310 List<Enrollment> values = null; 311 if (request instanceof CourseRequest) { 312 CourseRequest courseRequest = (CourseRequest) request; 313 if (!courseRequest.getSelectedChoices().isEmpty()) { 314 values = courseRequest.getSelectedEnrollments(iAssignment, true); 315 if (values != null && !values.isEmpty()) { 316 boolean hasNoConflictValue = false; 317 for (Enrollment enrollment : values) { 318 if (inConflict(idx, enrollment)) 319 continue; 320 hasNoConflictValue = true; 321 iCurrentAssignment[idx] = enrollment; 322 backTrack(idx + 1); 323 iCurrentAssignment[idx] = null; 324 } 325 if (hasNoConflictValue && iBranchWhenSelectedHasNoConflict) 326 return; 327 } 328 } 329 values = iValues.get(courseRequest); 330 if (values == null) { 331 values = values(courseRequest); 332 iValues.put(courseRequest, values); 333 } 334 } else { 335 values = request.computeEnrollments(iAssignment); 336 } 337 338 boolean hasNoConflictValue = false; 339 for (Enrollment enrollment : values) { 340 if (inConflict(idx, enrollment)) 341 continue; 342 hasNoConflictValue = true; 343 iCurrentAssignment[idx] = enrollment; 344 backTrack(idx + 1); 345 iCurrentAssignment[idx] = null; 346 } 347 348 if (canLeaveUnassigned(request) || (!hasNoConflictValue && request instanceof CourseRequest)) 349 backTrack(idx + 1); 350 } 351 352 /** 353 * Enrollment comparator 354 */ 355 public interface SelectionComparator { 356 /** 357 * Compare two enrollments 358 * 359 * @param assignment 360 * current assignment 361 * @param e1 362 * first enrollment 363 * @param e2 364 * second enrollment 365 * @return -1 if the first enrollment is better than the second etc. 366 */ 367 public int compare(Assignment<Request, Enrollment> assignment, Enrollment e1, Enrollment e2); 368 } 369 370 /** 371 * Multi-criteria selection interface. 372 */ 373 public interface SelectionCriterion extends SelectionComparator { 374 /** 375 * Compare two solutions 376 * 377 * @param assignment 378 * current assignment 379 * @param current 380 * current solution 381 * @param best 382 * best known solution 383 * @return true if current solution is better than the best one 384 */ 385 public int compare(Assignment<Request, Enrollment> assignment, Enrollment[] current, Enrollment[] best); 386 387 /** 388 * Bound 389 * 390 * @param assignment 391 * current assignment 392 * @param idx 393 * current request index 394 * @param current 395 * current solution 396 * @param best 397 * best known solution 398 * @return if the current solution can be extended and possibly improve 399 * upon the best known solution 400 */ 401 public boolean canImprove(Assignment<Request, Enrollment> assignment, int idx, Enrollment[] current, 402 Enrollment[] best); 403 404 /** 405 * For backward compatibility, return a weighted sum 406 * 407 * @param assignment 408 * current assignment 409 * @param enrollments 410 * current solution 411 * @return solution weight (weighted sum) 412 */ 413 public double getTotalWeight(Assignment<Request, Enrollment> assignment, Enrollment[] enrollments); 414 } 415 416 @Override 417 public void setRequiredUnassinged(Set<CourseRequest> requiredUnassignedRequests) { 418 iRequiredUnassinged = requiredUnassignedRequests; 419 } 420 421 @Override 422 public void setMaxOverExpected(double maxOverExpected) { 423 iMaxOverExpected = maxOverExpected; 424 } 425}