001 package net.sf.cpsolver.exam.neighbours;
002
003 import java.util.ArrayList;
004 import java.util.HashMap;
005 import java.util.HashSet;
006 import java.util.List;
007 import java.util.Map;
008 import java.util.Set;
009
010 import net.sf.cpsolver.exam.criteria.DistributionPenalty;
011 import net.sf.cpsolver.exam.criteria.RoomPenalty;
012 import net.sf.cpsolver.exam.criteria.RoomSizePenalty;
013 import net.sf.cpsolver.exam.model.Exam;
014 import net.sf.cpsolver.exam.model.ExamDistributionConstraint;
015 import net.sf.cpsolver.exam.model.ExamModel;
016 import net.sf.cpsolver.exam.model.ExamPeriodPlacement;
017 import net.sf.cpsolver.exam.model.ExamPlacement;
018 import net.sf.cpsolver.exam.model.ExamRoomPlacement;
019 import net.sf.cpsolver.exam.model.ExamRoomSharing;
020 import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
021 import net.sf.cpsolver.ifs.model.LazySwap;
022 import net.sf.cpsolver.ifs.model.Neighbour;
023 import net.sf.cpsolver.ifs.solution.Solution;
024 import net.sf.cpsolver.ifs.solver.Solver;
025 import net.sf.cpsolver.ifs.util.DataProperties;
026 import net.sf.cpsolver.ifs.util.ToolBox;
027
028 /**
029 * Try to swap a period between two exams.
030 * Two examinations are randomly selected. A new placement is generated by swapping periods of the two exams.
031 * For each exam, the best possible room placement is found. If the two exams are in the same period, it just tries
032 * to change the room assignments by looking for the best available room placement ignoring the existing room assignments
033 * of the two exams. If no conflict results from the swap the assignment is returned.
034 * The following exams of the second exam in the pair are tried for an exam swap otherwise.
035 * <br><br>
036 *
037 * @version ExamTT 1.2 (Examination Timetabling)<br>
038 * Copyright (C) 2013 Tomas Muller<br>
039 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
040 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
041 * <br>
042 * This library is free software; you can redistribute it and/or modify
043 * it under the terms of the GNU Lesser General Public License as
044 * published by the Free Software Foundation; either version 3 of the
045 * License, or (at your option) any later version. <br>
046 * <br>
047 * This library is distributed in the hope that it will be useful, but
048 * WITHOUT ANY WARRANTY; without even the implied warranty of
049 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
050 * Lesser General Public License for more details. <br>
051 * <br>
052 * You should have received a copy of the GNU Lesser General Public
053 * License along with this library; if not see
054 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
055 */
056 public class ExamPeriodSwapMove implements NeighbourSelection<Exam,ExamPlacement> {
057 private boolean iCheckStudentConflicts = false;
058 private boolean iCheckDistributionConstraints = true;
059
060 /**
061 * Constructor
062 * @param properties problem properties
063 */
064 public ExamPeriodSwapMove(DataProperties properties) {
065 iCheckStudentConflicts = properties.getPropertyBoolean("ExamPeriodSwapMove.CheckStudentConflicts", iCheckStudentConflicts);
066 iCheckDistributionConstraints = properties.getPropertyBoolean("ExamPeriodSwapMove.CheckDistributionConstraints", iCheckDistributionConstraints);
067 }
068
069 /**
070 * Initialization
071 */
072 @Override
073 public void init(Solver<Exam,ExamPlacement> solver) {}
074
075 /**
076 * Select an exam randomly,
077 * select an available period randomly (if it is not assigned),
078 * use rooms if possible, select rooms using {@link Exam#findBestAvailableRooms(ExamPeriodPlacement)} if not (exam is unassigned, a room is not available or used).
079 */
080 @Override
081 public Neighbour<Exam,ExamPlacement> selectNeighbour(Solution<Exam,ExamPlacement> solution) {
082 ExamModel model = (ExamModel)solution.getModel();
083 Exam x1 = ToolBox.random(model.variables());
084 if (x1.getAssignment() == null) return null;
085 int x = ToolBox.random(model.variables().size());
086 for (int v = 0; v < model.variables().size(); v++) {
087 Exam x2 = model.variables().get((v + x) % (model.variables().size()));
088 if (x1.equals(x2) || x2.getAssignment() == null) continue;
089 ExamPeriodPlacement p1 = x1.getPeriodPlacement(x2.getAssignment().getPeriod());
090 ExamPeriodPlacement p2 = x2.getPeriodPlacement(x1.getAssignment().getPeriod());
091 if (p1 == null || p2 == null) continue;
092 if (iCheckStudentConflicts && (x1.countStudentConflicts(p1) > 0 || x2.countStudentConflicts(p2) > 0)) continue;
093 if (iCheckDistributionConstraints) {
094 Map<Exam, ExamPlacement> placements = new HashMap<Exam, ExamPlacement>();
095 placements.put(x1, new ExamPlacement(x1, p1, new HashSet<ExamRoomPlacement>()));
096 placements.put(x2, new ExamPlacement(x2, p2, new HashSet<ExamRoomPlacement>()));
097 if (!checkDistributionConstraints(x1, p1, placements) || !checkDistributionConstraints(x2, p2, placements)) continue;
098 }
099 Set<ExamPlacement> conflicts = new HashSet<ExamPlacement>();
100 conflicts.add(x1.getAssignment()); conflicts.add(x2.getAssignment());
101 Map<Exam, ExamPlacement> placements = new HashMap<Exam, ExamPlacement>();
102 Set<ExamRoomPlacement> r1 = findBestAvailableRooms(x1, p1, conflicts, placements);
103 if (r1 == null) continue;
104 placements.put(x1, new ExamPlacement(x1, p1, r1));
105 Set<ExamRoomPlacement> r2 = findBestAvailableRooms(x2, p2, conflicts, placements);
106 if (r2 == null) continue;
107 return new LazySwap<Exam, ExamPlacement>(new ExamPlacement(x1, p1, r1), new ExamPlacement(x2, p2, r2));
108 }
109 return null;
110 }
111
112 public boolean checkDistributionConstraints(Exam exam, ExamPeriodPlacement period, Map<Exam, ExamPlacement> placements) {
113 for (ExamDistributionConstraint dc : exam.getDistributionConstraints()) {
114 if (!dc.isHard())
115 continue;
116 boolean before = true;
117 for (Exam other : dc.variables()) {
118 if (other.equals(this)) {
119 before = false;
120 continue;
121 }
122 ExamPlacement placement = (placements.containsKey(other) ? placements.get(other) : other.getAssignment());
123 if (placement == null) continue;
124 switch (dc.getType()) {
125 case ExamDistributionConstraint.sDistSamePeriod:
126 if (period.getIndex() != placement.getPeriod().getIndex())
127 return false;
128 break;
129 case ExamDistributionConstraint.sDistDifferentPeriod:
130 if (period.getIndex() == placement.getPeriod().getIndex())
131 return false;
132 break;
133 case ExamDistributionConstraint.sDistPrecedence:
134 if (before) {
135 if (period.getIndex() <= placement.getPeriod().getIndex())
136 return false;
137 } else {
138 if (period.getIndex() >= placement.getPeriod().getIndex())
139 return false;
140 }
141 break;
142 case ExamDistributionConstraint.sDistPrecedenceRev:
143 if (before) {
144 if (period.getIndex() >= placement.getPeriod().getIndex())
145 return false;
146 } else {
147 if (period.getIndex() <= placement.getPeriod().getIndex())
148 return false;
149 }
150 break;
151 }
152 }
153 }
154 return true;
155 }
156
157 public boolean checkDistributionConstraints(Exam exam, ExamRoomPlacement room, Set<ExamPlacement> conflictsToIgnore, Map<Exam, ExamPlacement> placements) {
158 for (ExamDistributionConstraint dc : exam.getDistributionConstraints()) {
159 if (!dc.isHard())
160 continue;
161 for (Exam other : dc.variables()) {
162 if (other.equals(exam)) continue;
163 ExamPlacement placement = (placements.containsKey(other) ? placements.get(other) : other.getAssignment());
164 if (placement == null || conflictsToIgnore.contains(placement)) continue;
165 switch (dc.getType()) {
166 case ExamDistributionConstraint.sDistSameRoom:
167 if (!placement.getRoomPlacements().contains(room))
168 return false;
169 break;
170 case ExamDistributionConstraint.sDistDifferentRoom:
171 if (placement.getRoomPlacements().contains(room))
172 return false;
173 break;
174 }
175 }
176 }
177 return true;
178 }
179
180 public int getDistributionConstraintPenalty(Exam exam, ExamRoomPlacement room, Set<ExamPlacement> conflictsToIgnore, Map<Exam, ExamPlacement> placements) {
181 int penalty = 0;
182 for (ExamDistributionConstraint dc : exam.getDistributionConstraints()) {
183 if (dc.isHard()) continue;
184 for (Exam other : dc.variables()) {
185 if (other.equals(this)) continue;
186 ExamPlacement placement = (placements.containsKey(other) ? placements.get(other) : other.getAssignment());
187 if (placement == null || conflictsToIgnore.contains(placement)) continue;
188 switch (dc.getType()) {
189 case ExamDistributionConstraint.sDistSameRoom:
190 if (!placement.getRoomPlacements().contains(room))
191 penalty += dc.getWeight();
192 break;
193 case ExamDistributionConstraint.sDistDifferentRoom:
194 if (placement.getRoomPlacements().contains(room))
195 penalty += dc.getWeight();
196 break;
197 }
198 }
199 }
200 return penalty;
201 }
202
203 public Set<ExamRoomPlacement> findBestAvailableRooms(Exam exam, ExamPeriodPlacement period, Set<ExamPlacement> conflictsToIgnore, Map<Exam, ExamPlacement> placements) {
204 if (exam.getMaxRooms() == 0)
205 return new HashSet<ExamRoomPlacement>();
206 double sw = exam.getModel().getCriterion(RoomSizePenalty.class).getWeight();
207 double pw = exam.getModel().getCriterion(RoomPenalty.class).getWeight();
208 double cw = exam.getModel().getCriterion(DistributionPenalty.class).getWeight();
209 ExamRoomSharing sharing = ((ExamModel)exam.getModel()).getRoomSharing();
210 loop: for (int nrRooms = 1; nrRooms <= exam.getMaxRooms(); nrRooms++) {
211 HashSet<ExamRoomPlacement> rooms = new HashSet<ExamRoomPlacement>();
212 int size = 0;
213 while (rooms.size() < nrRooms && size < exam.getSize()) {
214 int minSize = (exam.getSize() - size) / (nrRooms - rooms.size());
215 ExamRoomPlacement best = null;
216 double bestWeight = 0;
217 int bestSize = 0;
218 for (ExamRoomPlacement room : exam.getRoomPlacements()) {
219 if (!room.isAvailable(period.getPeriod())) continue;
220 if (rooms.contains(room)) continue;
221
222 List<ExamPlacement> overlaps = new ArrayList<ExamPlacement>();
223 for (ExamPlacement overlap: room.getRoom().getPlacements(period.getPeriod()))
224 if (!conflictsToIgnore.contains(overlap)) overlaps.add(overlap);
225 for (ExamPlacement other: placements.values())
226 if (other.getPeriod().equals(period.getPeriod()))
227 for (ExamRoomPlacement r: other.getRoomPlacements())
228 if (r.getRoom().equals(room.getRoom())) {
229 overlaps.add(other);
230 continue;
231 }
232
233 if (nrRooms == 1 && sharing != null) {
234 if (sharing.inConflict(exam, overlaps, room.getRoom()))
235 continue;
236 } else {
237 if (!overlaps.isEmpty())
238 continue;
239 }
240 if (iCheckDistributionConstraints && !checkDistributionConstraints(exam, room, conflictsToIgnore, placements)) continue;
241 int s = room.getSize(exam.hasAltSeating());
242 if (s < minSize) break;
243 int p = room.getPenalty(period.getPeriod());
244 double w = pw * p + sw * (s - minSize) + cw * getDistributionConstraintPenalty(exam, room, conflictsToIgnore, placements);
245 double d = 0;
246 if (!rooms.isEmpty()) {
247 for (ExamRoomPlacement r : rooms) {
248 d += r.getDistanceInMeters(room);
249 }
250 w += d / rooms.size();
251 }
252 if (best == null || bestWeight > w) {
253 best = room;
254 bestSize = s;
255 bestWeight = w;
256 }
257 }
258 if (best == null)
259 continue loop;
260 rooms.add(best);
261 size += bestSize;
262 }
263 if (size >= exam.getSize())
264 return rooms;
265 }
266 return null;
267 }
268 }