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