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