001package org.cpsolver.studentsct.heuristics.selection; 002 003import java.util.ArrayList; 004import java.util.Collections; 005import java.util.Comparator; 006import java.util.ConcurrentModificationException; 007import java.util.HashMap; 008import java.util.Iterator; 009import java.util.LinkedList; 010import java.util.List; 011import java.util.Queue; 012import java.util.concurrent.locks.Lock; 013 014import org.cpsolver.ifs.assignment.Assignment; 015import org.cpsolver.ifs.heuristics.BacktrackNeighbourSelection; 016import org.cpsolver.ifs.heuristics.NeighbourSelection; 017import org.cpsolver.ifs.model.Neighbour; 018import org.cpsolver.ifs.solution.Solution; 019import org.cpsolver.ifs.solver.Solver; 020import org.cpsolver.ifs.util.DataProperties; 021import org.cpsolver.ifs.util.Progress; 022import org.cpsolver.studentsct.StudentSectioningModel; 023import org.cpsolver.studentsct.model.CourseRequest; 024import org.cpsolver.studentsct.model.Enrollment; 025import org.cpsolver.studentsct.model.Request; 026 027/** 028 * Swap enrollments of different students of a course. This is to improve 029 * the enrollment alternativity {@link Enrollment#getPriority()} as well as 030 * selection preferences {@link Enrollment#percentSelected()}. 031 * 032 * <br> 033 * <br> 034 * 035 * @version StudentSct 1.3 (Student Sectioning)<br> 036 * Copyright (C) 2007 - 2018 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 052 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 053 */ 054 055public class StudentEnrollmentSwapSelection implements NeighbourSelection<Request, Enrollment> { 056 private Selection iSelection = null; 057 protected Queue<Request> iRequests = null; 058 059 public StudentEnrollmentSwapSelection(DataProperties properties) { 060 } 061 062 public void init(Solver<Request, Enrollment> solver, String name) { 063 List<Request> variables = new ArrayList<Request>(solver.currentSolution().getModel().assignedVariables(solver.currentSolution().getAssignment())); 064 Collections.shuffle(variables); 065 iRequests = new LinkedList<Request>(variables); 066 if (iSelection == null) { 067 try { 068 iSelection = new Selection(solver.getProperties()); 069 iSelection.init(solver); 070 } catch (Exception e) { 071 throw new RuntimeException(e.getMessage(), e); 072 } 073 } 074 Progress.getInstance(solver.currentSolution().getModel()).setPhase(name, variables.size()); 075 } 076 077 @Override 078 public void init(Solver<Request, Enrollment> solver) { 079 init(solver, "Enrollment swaps..."); 080 } 081 082 protected synchronized Request nextRequest() { 083 return iRequests.poll(); 084 } 085 086 public synchronized void addRequest(Request request) { 087 if (iRequests != null) iRequests.add(request); 088 } 089 090 @Override 091 public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) { 092 Request request = null; 093 while ((request = nextRequest()) != null) { 094 Progress.getInstance(solution.getModel()).incProgress(); 095 if (request instanceof CourseRequest) { 096 try { 097 Enrollment e = request.getAssignment(solution.getAssignment()); 098 if (e == null || e.getPriority() > 0 || !((CourseRequest)request).getSelectedChoices().isEmpty()) { 099 Neighbour<Request, Enrollment> n = iSelection.selectNeighbour(solution, request); 100 if (n != null && n.value(solution.getAssignment()) <= 0.0) 101 return n; 102 } 103 } catch (ConcurrentModificationException e) { 104 addRequest(request); 105 } 106 } 107 } 108 return null; 109 } 110 111 class Selection extends BacktrackNeighbourSelection<Request, Enrollment> { 112 private int iMaxValues = 1000; 113 114 Selection(DataProperties properties) throws Exception { 115 super(properties); 116 setTimeout(properties.getPropertyInt("Neighbour.EnrollmentSwapTimeout", 500)); 117 iMaxValues = properties.getPropertyInt("Neighbour.EnrollmentSwapMaxValues", iMaxValues); 118 } 119 120 @Override 121 protected Iterator<Enrollment> values(BacktrackNeighbourSelection<Request, Enrollment>.BacktrackNeighbourSelectionContext context, Request variable) { 122 if (variable instanceof CourseRequest) { 123 final CourseRequest request = (CourseRequest)variable; 124 final StudentSectioningModel model = (StudentSectioningModel)context.getModel(); 125 final Assignment<Request, Enrollment> assignment = context.getAssignment(); 126 List<Enrollment> values = null; 127 Enrollment current = request.getAssignment(context.getAssignment()); 128 if (!request.getSelectedChoices().isEmpty() && current != null && current.getPriority() == 0) { 129 values = request.getSelectedEnrollments(assignment, false); 130 } else { 131 values = (iMaxValues > 0 ? request.computeRandomEnrollments(assignment, iMaxValues) : request.computeEnrollments(assignment)); 132 } 133 Collections.sort(values, new Comparator<Enrollment>() { 134 private HashMap<Enrollment, Double> iValues = new HashMap<Enrollment, Double>(); 135 private Double value(Enrollment e) { 136 Double value = iValues.get(e); 137 if (value == null) { 138 if (model.getStudentQuality() != null) 139 value = model.getStudentWeights().getWeight(assignment, e, model.getStudentQuality().conflicts(e)); 140 else 141 value = model.getStudentWeights().getWeight(assignment, e, 142 (model.getDistanceConflict() == null ? null : model.getDistanceConflict().conflicts(e)), 143 (model.getTimeOverlaps() == null ? null : model.getTimeOverlaps().conflicts(e))); 144 iValues.put(e, value); 145 } 146 return value; 147 } 148 @Override 149 public int compare(Enrollment e1, Enrollment e2) { 150 if (e1.equals(assignment.getValue(request))) return -1; 151 if (e2.equals(assignment.getValue(request))) return 1; 152 Double v1 = value(e1), v2 = value(e2); 153 return v1.equals(v2) ? e1.compareTo(assignment, e2) : v2.compareTo(v1); 154 } 155 }); 156 return values.iterator(); 157 } else { 158 return variable.computeEnrollments(context.getAssignment()).iterator(); 159 } 160 } 161 162 @Override 163 protected void selectNeighbour(Solution<Request, Enrollment> solution, Request variable, BacktrackNeighbourSelectionContext context) { 164 Lock lock = solution.getLock().writeLock(); 165 lock.lock(); 166 try { 167 exploreEnrollmentSwaps(context, variable); 168 } finally { 169 lock.unlock(); 170 } 171 } 172 173 protected void exploreEnrollmentSwaps(BacktrackNeighbourSelectionContext context, Request variable) { 174 Enrollment current = context.getAssignment().getValue(variable); 175 double currentValue = (current == null ? 0.0 : current.toDouble(context.getAssignment())); 176 for (Iterator<Enrollment> e = values(context, variable); canContinueEvaluation(context) && e.hasNext();) { 177 Enrollment value = e.next(); 178 if (value.equals(current)) continue; 179 if (current != null && currentValue <= value.toDouble(context.getAssignment())) continue; 180 if (context.isTimeoutReached() || context.isMaxItersReached()) break; 181 context.incIteration(); 182 if (context.getModel().inConflict(context.getAssignment(), value)) { 183 for (Enrollment other: new ArrayList<Enrollment>(value.getCourse().getContext(context.getAssignment()).getEnrollments())) { 184 if (other.getStudent().equals(value.getStudent()) || !other.getSections().equals(value.getSections())) continue; 185 context.getAssignment().unassign(0, other.variable()); 186 if (!context.getModel().inConflict(context.getAssignment(), value)) { 187 if (current != null) 188 context.getAssignment().unassign(0, current.variable()); 189 context.getAssignment().assign(0, value); 190 for (Iterator<Enrollment> f = values(context, other.variable()); canContinueEvaluation(context) && f.hasNext();) { 191 Enrollment fix = f.next(); 192 if (!context.getModel().inConflict(context.getAssignment(), fix)) { 193 context.getAssignment().assign(0, fix); 194 context.saveBest(variable, other.variable()); 195 context.getAssignment().unassign(0, fix.variable()); 196 } 197 } 198 if (current == null) 199 context.getAssignment().unassign(0, variable); 200 else 201 context.getAssignment().assign(0, current); 202 } 203 context.getAssignment().assign(0, other); 204 } 205 } else { 206 if (current != null) 207 context.getAssignment().unassign(0, current.variable()); 208 context.getAssignment().assign(0, value); 209 context.saveBest(variable); 210 if (current == null) 211 context.getAssignment().unassign(0, variable); 212 else 213 context.getAssignment().assign(0, current); 214 } 215 } 216 } 217 } 218 219}