001package org.cpsolver.studentsct.heuristics.selection; 002 003import java.text.DecimalFormat; 004import java.util.ArrayList; 005import java.util.Collection; 006import java.util.Collections; 007import java.util.Comparator; 008import java.util.ConcurrentModificationException; 009import java.util.HashMap; 010import java.util.Iterator; 011import java.util.LinkedList; 012import java.util.List; 013import java.util.ListIterator; 014import java.util.Map; 015import java.util.concurrent.locks.Lock; 016 017import org.cpsolver.ifs.assignment.Assignment; 018import org.cpsolver.ifs.heuristics.BacktrackNeighbourSelection; 019import org.cpsolver.ifs.heuristics.NeighbourSelection; 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.solver.SolverListener; 025import org.cpsolver.ifs.util.DataProperties; 026import org.cpsolver.ifs.util.Progress; 027import org.cpsolver.studentsct.StudentSectioningModel; 028import org.cpsolver.studentsct.heuristics.selection.BacktrackSelection.RequestComparator; 029import org.cpsolver.studentsct.model.CourseRequest; 030import org.cpsolver.studentsct.model.Enrollment; 031import org.cpsolver.studentsct.model.Request; 032import org.cpsolver.studentsct.model.Request.RequestPriority; 033import org.cpsolver.studentsct.model.Student.StudentPriority; 034 035/** 036 * Swap enrollments of different students of a course. This is to improve 037 * the enrollment alternativity {@link Enrollment#getPriority()} as well as 038 * selection preferences {@link Enrollment#percentSelected()}. 039 * 040 * <br> 041 * <br> 042 * 043 * @author Tomáš Müller 044 * @version StudentSct 1.3 (Student Sectioning)<br> 045 * Copyright (C) 2007 - 2018 Tomáš Müller<br> 046 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 047 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 048 * <br> 049 * This library is free software; you can redistribute it and/or modify 050 * it under the terms of the GNU Lesser General Public License as 051 * published by the Free Software Foundation; either version 3 of the 052 * License, or (at your option) any later version. <br> 053 * <br> 054 * This library is distributed in the hope that it will be useful, but 055 * WITHOUT ANY WARRANTY; without even the implied warranty of 056 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 057 * Lesser General Public License for more details. <br> 058 * <br> 059 * You should have received a copy of the GNU Lesser General Public 060 * License along with this library; if not see 061 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 062 */ 063 064public class StudentEnrollmentSwapSelection implements NeighbourSelection<Request, Enrollment>, InfoProvider<Request, Enrollment>, SolverListener<Request, Enrollment> { 065 private static DecimalFormat sDF = new DecimalFormat("0.00"); 066 private Selection iSelection = null; 067 protected LinkedList<Request> iRequests = null; 068 069 protected long iNbrIterations = 0; 070 protected long iTotalTime = 0; 071 protected long iNbrTimeoutReached = 0; 072 protected long iNbrNoSolution = 0; 073 protected RequestComparator iRequestComparator; 074 075 public StudentEnrollmentSwapSelection(DataProperties properties) { 076 iRequestComparator = new RequestComparator(properties); 077 } 078 079 public void init(Solver<Request, Enrollment> solver, String name) { 080 List<Request> variables = new ArrayList<Request>(solver.currentSolution().getModel().assignedVariables(solver.currentSolution().getAssignment())); 081 Collections.shuffle(variables); 082 Collections.sort(variables, iRequestComparator); 083 iRequests = new LinkedList<Request>(variables); 084 if (iSelection == null) { 085 try { 086 iSelection = new Selection(solver.getProperties()); 087 iSelection.init(solver); 088 } catch (Exception e) { 089 throw new RuntimeException(e.getMessage(), e); 090 } 091 } 092 Progress.getInstance(solver.currentSolution().getModel()).setPhase(name, variables.size()); 093 iNbrIterations = 0; 094 iNbrTimeoutReached = 0; 095 iNbrNoSolution = 0; 096 iTotalTime = 0; 097 } 098 099 @Override 100 public void init(Solver<Request, Enrollment> solver) { 101 init(solver, "Enrollment swaps..."); 102 } 103 104 protected synchronized Request nextRequest() { 105 return iRequests.poll(); 106 } 107 108 public synchronized void addRequest(Request request) { 109 if (iRequests != null && request != null && !request.getStudent().isDummy()) { 110 if (request.getStudent().getPriority().ordinal() < StudentPriority.Normal.ordinal() || request.getRequestPriority().ordinal() < RequestPriority.Normal.ordinal()) { 111 for (ListIterator<Request> i = iRequests.listIterator(); i.hasNext();) { 112 Request r = i.next(); 113 if (iRequestComparator.compare(r, request) > 0) { 114 i.previous(); // go one back 115 i.add(request); 116 return; 117 } 118 } 119 } 120 iRequests.add(request); 121 } 122 } 123 124 @Override 125 public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) { 126 Request request = null; 127 while ((request = nextRequest()) != null) { 128 Progress p = Progress.getInstance(solution.getModel()); 129 p.incProgress(); 130 if (p.getProgress() > 2.0 * p.getProgressMax()) return null; 131 if (request instanceof CourseRequest) { 132 try { 133 Enrollment e = request.getAssignment(solution.getAssignment()); 134 if (e == null || e.getPriority() > 0 || !((CourseRequest)request).getSelectedChoices().isEmpty()) { 135 Neighbour<Request, Enrollment> n = iSelection.selectNeighbour(solution, request); 136 if (iSelection.getContext() != null) { 137 iNbrIterations ++; 138 iTotalTime += iSelection.getContext().getTime(); 139 if (iSelection.getContext().isTimeoutReached()) iNbrTimeoutReached ++; 140 if (n == null) iNbrNoSolution ++; 141 } 142 if (n != null && n.value(solution.getAssignment()) <= 0.0) 143 return n; 144 } 145 } catch (ConcurrentModificationException e) { 146 addRequest(request); 147 } 148 } 149 } 150 return null; 151 } 152 153 class Selection extends BacktrackNeighbourSelection<Request, Enrollment> { 154 private int iMaxValues = 1000; 155 156 Selection(DataProperties properties) throws Exception { 157 super(properties); 158 setTimeout(properties.getPropertyInt("Neighbour.EnrollmentSwapTimeout", 500)); 159 iMaxValues = properties.getPropertyInt("Neighbour.EnrollmentSwapMaxValues", iMaxValues); 160 } 161 162 @Override 163 protected Iterator<Enrollment> values(BacktrackNeighbourSelection<Request, Enrollment>.BacktrackNeighbourSelectionContext context, Request variable) { 164 if (variable instanceof CourseRequest) { 165 final CourseRequest request = (CourseRequest)variable; 166 final StudentSectioningModel model = (StudentSectioningModel)context.getModel(); 167 final Assignment<Request, Enrollment> assignment = context.getAssignment(); 168 List<Enrollment> values = null; 169 Enrollment current = request.getAssignment(context.getAssignment()); 170 if (!request.getSelectedChoices().isEmpty() && current != null && current.getPriority() == 0) { 171 values = request.getSelectedEnrollments(assignment, false); 172 } else { 173 values = (iMaxValues > 0 ? request.computeRandomEnrollments(assignment, iMaxValues) : request.computeEnrollments(assignment)); 174 } 175 Collections.sort(values, new Comparator<Enrollment>() { 176 private HashMap<Enrollment, Double> iValues = new HashMap<Enrollment, Double>(); 177 private Double value(Enrollment e) { 178 Double value = iValues.get(e); 179 if (value == null) { 180 if (model.getStudentQuality() != null) 181 value = model.getStudentWeights().getWeight(assignment, e, model.getStudentQuality().conflicts(e)); 182 else 183 value = model.getStudentWeights().getWeight(assignment, e, 184 (model.getDistanceConflict() == null ? null : model.getDistanceConflict().conflicts(e)), 185 (model.getTimeOverlaps() == null ? null : model.getTimeOverlaps().conflicts(e))); 186 iValues.put(e, value); 187 } 188 return value; 189 } 190 @Override 191 public int compare(Enrollment e1, Enrollment e2) { 192 if (e1.equals(assignment.getValue(request))) return -1; 193 if (e2.equals(assignment.getValue(request))) return 1; 194 Double v1 = value(e1), v2 = value(e2); 195 return v1.equals(v2) ? e1.compareTo(assignment, e2) : v2.compareTo(v1); 196 } 197 }); 198 return values.iterator(); 199 } else { 200 return variable.computeEnrollments(context.getAssignment()).iterator(); 201 } 202 } 203 204 @Override 205 protected void selectNeighbour(Solution<Request, Enrollment> solution, Request variable, BacktrackNeighbourSelectionContext context) { 206 iContext = context; 207 Lock lock = solution.getLock().writeLock(); 208 lock.lock(); 209 try { 210 exploreEnrollmentSwaps(context, variable); 211 } finally { 212 lock.unlock(); 213 } 214 } 215 216 protected void exploreEnrollmentSwaps(BacktrackNeighbourSelectionContext context, Request variable) { 217 Enrollment current = context.getAssignment().getValue(variable); 218 double currentValue = (current == null ? 0.0 : current.toDouble(context.getAssignment())); 219 for (Iterator<Enrollment> e = values(context, variable); canContinueEvaluation(context) && e.hasNext();) { 220 Enrollment value = e.next(); 221 if (value.equals(current)) continue; 222 boolean hasChildren = (value.getCourse() != null && value.getCourse().hasChildren()); 223 if (current != null && currentValue <= value.toDouble(context.getAssignment())) continue; 224 if (context.isTimeoutReached() || context.isMaxItersReached()) break; 225 context.incIteration(); 226 if (context.getModel().inConflict(context.getAssignment(), value)) { 227 other: for (Enrollment other: new ArrayList<Enrollment>(value.getCourse().getContext(context.getAssignment()).getEnrollments())) { 228 if (other.getStudent().equals(value.getStudent()) || !other.getSections().equals(value.getSections())) continue; 229 if (hasChildren) { 230 for (Request r: other.getStudent().getRequests()) { 231 if (r.equals(other.getRequest())) continue; 232 Enrollment f = context.getAssignment().getValue(r); 233 if (f != null && f.getCourse() != null && value.getCourse().equals(f.getCourse().getParent())) { 234 continue other; 235 } 236 } 237 } 238 context.getAssignment().unassign(0, other.variable()); 239 if (!context.getModel().inConflict(context.getAssignment(), value)) { 240 if (current != null) 241 context.getAssignment().unassign(0, current.variable()); 242 context.getAssignment().assign(0, value); 243 for (Iterator<Enrollment> f = values(context, other.variable()); canContinueEvaluation(context) && f.hasNext();) { 244 Enrollment fix = f.next(); 245 if (!context.getModel().inConflict(context.getAssignment(), fix)) { 246 context.getAssignment().assign(0, fix); 247 context.saveBest(variable, other.variable()); 248 context.getAssignment().unassign(0, fix.variable()); 249 } 250 } 251 if (current == null) 252 context.getAssignment().unassign(0, variable); 253 else 254 context.getAssignment().assign(0, current); 255 } 256 context.getAssignment().assign(0, other); 257 } 258 } else { 259 if (current != null) 260 context.getAssignment().unassign(0, current.variable()); 261 context.getAssignment().assign(0, value); 262 context.saveBest(variable); 263 if (current == null) 264 context.getAssignment().unassign(0, variable); 265 else 266 context.getAssignment().assign(0, current); 267 } 268 } 269 } 270 } 271 272 @Override 273 public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info) { 274 if (iNbrIterations > 0) 275 info.put("Timing of " + getClass().getSimpleName(), sDF.format(((double)iTotalTime) / iNbrIterations) + " ms/it (" + 276 iNbrIterations + " iterations, " + 277 (iNbrNoSolution == 0 ? "" : sDF.format(100.0 * iNbrNoSolution / iNbrIterations) + "% no solution, ") + 278 sDF.format(100.0 * iNbrTimeoutReached / iNbrIterations) + "% time limit of " + sDF.format(iSelection.getTimeout() / 1000.0) + " seconds reached)"); 279 } 280 281 @Override 282 public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info, Collection<Request> variables) { 283 } 284 285 @Override 286 public boolean variableSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable) { 287 return false; 288 } 289 @Override 290 public boolean valueSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable, Enrollment value) { 291 return false; 292 } 293 @Override 294 public boolean neighbourSelected(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) { 295 return false; 296 } 297 @Override 298 public void neighbourFailed(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) { 299 if (neighbour instanceof BacktrackNeighbourSelection.BackTrackNeighbour) 300 addRequest(((BacktrackNeighbourSelection<Request, Enrollment>.BackTrackNeighbour)neighbour).getAssignments().get(0).getRequest()); 301 } 302}