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 063 /** Student */ 064 protected Student iStudent; 065 /** Start time */ 066 protected long iT0; 067 /** End time */ 068 protected long iT1; 069 /** Was timeout reached */ 070 protected boolean iTimeoutReached; 071 /** Current assignment */ 072 protected Enrollment[] iCurrentAssignment; 073 /** Best assignment */ 074 protected Enrollment[] iBestAssignment; 075 /** Value cache */ 076 protected HashMap<CourseRequest, List<Enrollment>> iValues; 077 078 private Set<FreeTimeRequest> iRequiredFreeTimes; 079 private Hashtable<CourseRequest, Set<Section>> iPreferredSections; 080 private Hashtable<CourseRequest, Config> iRequiredConfig = new Hashtable<CourseRequest, Config>(); 081 private Hashtable<CourseRequest, Hashtable<Subpart, Section>> iRequiredSection = new Hashtable<CourseRequest, Hashtable<Subpart, Section>>(); 082 private Set<CourseRequest> iRequiredUnassinged = null; 083 084 public MultiCriteriaBranchAndBoundSelection(DataProperties config) { 085 iTimeout = config.getPropertyInt("Neighbour.BranchAndBoundTimeout", iTimeout); 086 iPriorityWeighting = config.getPropertyBoolean("StudentWeights.PriorityWeighting", iPriorityWeighting); 087 iBranchWhenSelectedHasNoConflict = config.getPropertyBoolean("Students.BranchWhenSelectedHasNoConflict", iBranchWhenSelectedHasNoConflict); 088 } 089 090 @Override 091 public void setModel(OnlineSectioningModel model) { 092 iModel = model; 093 } 094 095 @Override 096 public void setPreferredSections(Hashtable<CourseRequest, Set<Section>> preferredSections) { 097 iPreferredSections = preferredSections; 098 } 099 100 public void setTimeout(int timeout) { 101 iTimeout = timeout; 102 } 103 104 @Override 105 public void setRequiredSections(Hashtable<CourseRequest, Set<Section>> requiredSections) { 106 if (requiredSections != null) { 107 for (Map.Entry<CourseRequest, Set<Section>> entry : requiredSections.entrySet()) { 108 Hashtable<Subpart, Section> subSection = new Hashtable<Subpart, Section>(); 109 iRequiredSection.put(entry.getKey(), subSection); 110 for (Section section : entry.getValue()) { 111 if (subSection.isEmpty()) 112 iRequiredConfig.put(entry.getKey(), section.getSubpart().getConfig()); 113 subSection.put(section.getSubpart(), section); 114 } 115 } 116 } 117 } 118 119 @Override 120 public void setRequiredFreeTimes(Set<FreeTimeRequest> requiredFreeTimes) { 121 iRequiredFreeTimes = requiredFreeTimes; 122 } 123 124 public BranchBoundNeighbour select(Assignment<Request, Enrollment> assignment, Student student, 125 SelectionCriterion comparator) { 126 iStudent = student; 127 iComparator = comparator; 128 iAssignment = assignment; 129 return select(); 130 } 131 132 @Override 133 public BranchBoundNeighbour select(Assignment<Request, Enrollment> assignment, Student student) { 134 SelectionCriterion comparator = null; 135 if (iPriorityWeighting) 136 comparator = new OnlineSectioningCriterion(student, iModel, assignment, iPreferredSections); 137 else 138 comparator = new EqualWeightCriterion(student, iModel, assignment, iPreferredSections); 139 return select(assignment, student, comparator); 140 } 141 142 /** 143 * Execute branch & bound, return the best found schedule for the selected 144 * student. 145 */ 146 public BranchBoundNeighbour select() { 147 iT0 = JProf.currentTimeMillis(); 148 iTimeoutReached = false; 149 iCurrentAssignment = new Enrollment[iStudent.getRequests().size()]; 150 iBestAssignment = null; 151 152 int i = 0; 153 for (Request r : iStudent.getRequests()) 154 iCurrentAssignment[i++] = iAssignment.getValue(r); 155 saveBest(); 156 for (int j = 0; j < iCurrentAssignment.length; j++) 157 iCurrentAssignment[j] = null; 158 159 iValues = new HashMap<CourseRequest, List<Enrollment>>(); 160 backTrack(0); 161 iT1 = JProf.currentTimeMillis(); 162 if (iBestAssignment == null) 163 return null; 164 165 return new BranchBoundNeighbour(iStudent, iComparator.getTotalWeight(iAssignment, iBestAssignment), 166 iBestAssignment); 167 } 168 169 /** Was timeout reached */ 170 public boolean isTimeoutReached() { 171 return iTimeoutReached; 172 } 173 174 /** Time (in milliseconds) the branch & bound did run */ 175 public long getTime() { 176 return iT1 - iT0; 177 } 178 179 /** Save the current schedule as the best */ 180 public void saveBest() { 181 if (iBestAssignment == null) 182 iBestAssignment = new Enrollment[iCurrentAssignment.length]; 183 for (int i = 0; i < iCurrentAssignment.length; i++) 184 iBestAssignment[i] = iCurrentAssignment[i]; 185 } 186 187 /** True if the enrollment is conflicting */ 188 public boolean inConflict(final int idx, final Enrollment enrollment) { 189 for (GlobalConstraint<Request, Enrollment> constraint : enrollment.variable().getModel().globalConstraints()) 190 if (constraint.inConflict(iAssignment, enrollment)) 191 return true; 192 for (LinkedSections linkedSections : iStudent.getLinkedSections()) { 193 if (linkedSections.inConflict(enrollment, new LinkedSections.EnrollmentAssignment() { 194 @Override 195 public Enrollment getEnrollment(Request request, int index) { 196 return (index == idx ? enrollment : iCurrentAssignment[index]); 197 } 198 }) != null) 199 return true; 200 } 201 for (int i = 0; i < iCurrentAssignment.length; i++) 202 if (iCurrentAssignment[i] != null && i != idx && iCurrentAssignment[i].isOverlapping(enrollment)) 203 return true; 204 return !isAllowed(idx, enrollment); 205 } 206 207 /** True if the given request can be assigned */ 208 public boolean canAssign(Request request, int idx) { 209 if (!request.isAlternative() || iCurrentAssignment[idx] != null) 210 return true; 211 int alt = 0; 212 int i = 0; 213 for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); i++) { 214 Request r = e.next(); 215 if (r.equals(request)) 216 continue; 217 if (r.isAlternative()) { 218 if (iCurrentAssignment[i] != null || (r instanceof CourseRequest && ((CourseRequest) r).isWaitlist())) 219 alt--; 220 } else { 221 if (r instanceof CourseRequest && !((CourseRequest) r).isWaitlist() && iCurrentAssignment[i] == null) 222 alt++; 223 } 224 } 225 return (alt > 0); 226 } 227 228 public boolean isAllowed(int idx, Enrollment enrollment) { 229 if (enrollment.isCourseRequest()) { 230 CourseRequest request = (CourseRequest) enrollment.getRequest(); 231 if (iRequiredUnassinged != null && iRequiredUnassinged.contains(request)) return false; 232 Config reqConfig = iRequiredConfig.get(request); 233 if (reqConfig != null) { 234 if (!reqConfig.equals(enrollment.getConfig())) 235 return false; 236 Hashtable<Subpart, Section> reqSections = iRequiredSection.get(request); 237 for (Section section : enrollment.getSections()) { 238 Section reqSection = reqSections.get(section.getSubpart()); 239 if (reqSection == null) 240 continue; 241 if (!section.equals(reqSection)) 242 return false; 243 } 244 } 245 } else if (iRequiredFreeTimes.contains(enrollment.getRequest())) { 246 if (enrollment.getAssignments() == null || enrollment.getAssignments().isEmpty()) 247 return false; 248 } 249 return true; 250 } 251 252 /** Returns true if the given request can be left unassigned */ 253 protected boolean canLeaveUnassigned(Request request) { 254 if (request instanceof CourseRequest) { 255 if (iRequiredConfig.get(request) != null) 256 return false; 257 } else if (iRequiredFreeTimes.contains(request)) 258 return false; 259 return true; 260 } 261 262 /** Returns list of available enrollments for a course request */ 263 protected List<Enrollment> values(final CourseRequest request) { 264 if (iRequiredUnassinged != null && iRequiredUnassinged.contains(request)) 265 return new ArrayList<Enrollment>(); 266 List<Enrollment> values = request.getAvaiableEnrollments(iAssignment); 267 Collections.sort(values, new Comparator<Enrollment>() { 268 @Override 269 public int compare(Enrollment o1, Enrollment o2) { 270 return iComparator.compare(iAssignment, o1, o2); 271 } 272 }); 273 return values; 274 } 275 276 /** branch & bound search */ 277 public void backTrack(int idx) { 278 if (iTimeout > 0 && (JProf.currentTimeMillis() - iT0) > iTimeout) { 279 iTimeoutReached = true; 280 return; 281 } 282 if (idx == iCurrentAssignment.length) { 283 if (iBestAssignment == null || iComparator.compare(iAssignment, iCurrentAssignment, iBestAssignment) < 0) 284 saveBest(); 285 return; 286 } else if (iBestAssignment != null 287 && !iComparator.canImprove(iAssignment, idx, iCurrentAssignment, iBestAssignment)) { 288 return; 289 } 290 291 Request request = iStudent.getRequests().get(idx); 292 if (!canAssign(request, idx)) { 293 backTrack(idx + 1); 294 return; 295 } 296 297 List<Enrollment> values = null; 298 if (request instanceof CourseRequest) { 299 CourseRequest courseRequest = (CourseRequest) request; 300 if (!courseRequest.getSelectedChoices().isEmpty()) { 301 values = courseRequest.getSelectedEnrollments(iAssignment, true); 302 if (values != null && !values.isEmpty()) { 303 boolean hasNoConflictValue = false; 304 for (Enrollment enrollment : values) { 305 if (inConflict(idx, enrollment)) 306 continue; 307 hasNoConflictValue = true; 308 iCurrentAssignment[idx] = enrollment; 309 backTrack(idx + 1); 310 iCurrentAssignment[idx] = null; 311 } 312 if (hasNoConflictValue && iBranchWhenSelectedHasNoConflict) 313 return; 314 } 315 } 316 values = iValues.get(courseRequest); 317 if (values == null) { 318 values = values(courseRequest); 319 iValues.put(courseRequest, values); 320 } 321 } else { 322 values = request.computeEnrollments(iAssignment); 323 } 324 325 boolean hasNoConflictValue = false; 326 for (Enrollment enrollment : values) { 327 if (inConflict(idx, enrollment)) 328 continue; 329 hasNoConflictValue = true; 330 iCurrentAssignment[idx] = enrollment; 331 backTrack(idx + 1); 332 iCurrentAssignment[idx] = null; 333 } 334 335 if (canLeaveUnassigned(request) || (!hasNoConflictValue && request instanceof CourseRequest)) 336 backTrack(idx + 1); 337 } 338 339 /** 340 * Enrollment comparator 341 */ 342 public interface SelectionComparator { 343 /** 344 * Compare two enrollments 345 * 346 * @param assignment 347 * current assignment 348 * @param e1 349 * first enrollment 350 * @param e2 351 * second enrollment 352 * @return -1 if the first enrollment is better than the second etc. 353 */ 354 public int compare(Assignment<Request, Enrollment> assignment, Enrollment e1, Enrollment e2); 355 } 356 357 /** 358 * Multi-criteria selection interface. 359 */ 360 public interface SelectionCriterion extends SelectionComparator { 361 /** 362 * Compare two solutions 363 * 364 * @param assignment 365 * current assignment 366 * @param current 367 * current solution 368 * @param best 369 * best known solution 370 * @return true if current solution is better than the best one 371 */ 372 public int compare(Assignment<Request, Enrollment> assignment, Enrollment[] current, Enrollment[] best); 373 374 /** 375 * Bound 376 * 377 * @param assignment 378 * current assignment 379 * @param idx 380 * current request index 381 * @param current 382 * current solution 383 * @param best 384 * best known solution 385 * @return if the current solution can be extended and possibly improve 386 * upon the best known solution 387 */ 388 public boolean canImprove(Assignment<Request, Enrollment> assignment, int idx, Enrollment[] current, 389 Enrollment[] best); 390 391 /** 392 * For backward compatibility, return a weighted sum 393 * 394 * @param assignment 395 * current assignment 396 * @param enrollments 397 * current solution 398 * @return solution weight (weighted sum) 399 */ 400 public double getTotalWeight(Assignment<Request, Enrollment> assignment, Enrollment[] enrollments); 401 } 402 403 @Override 404 public void setRequiredUnassinged(Set<CourseRequest> requiredUnassignedRequests) { 405 iRequiredUnassinged = requiredUnassignedRequests; 406 } 407}