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