001 package net.sf.cpsolver.exam.split;
002
003 import java.util.HashSet;
004 import java.util.List;
005 import java.util.Set;
006
007 import net.sf.cpsolver.exam.criteria.RoomPenalty;
008 import net.sf.cpsolver.exam.criteria.RoomSizePenalty;
009 import net.sf.cpsolver.exam.model.Exam;
010 import net.sf.cpsolver.exam.model.ExamPeriodPlacement;
011 import net.sf.cpsolver.exam.model.ExamPlacement;
012 import net.sf.cpsolver.exam.model.ExamRoomPlacement;
013 import net.sf.cpsolver.exam.model.ExamStudent;
014 import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
015 import net.sf.cpsolver.ifs.model.Neighbour;
016 import net.sf.cpsolver.ifs.solution.Solution;
017 import net.sf.cpsolver.ifs.solver.Solver;
018 import net.sf.cpsolver.ifs.util.DataProperties;
019 import net.sf.cpsolver.ifs.util.ToolBox;
020
021 import org.apache.log4j.Logger;
022
023 /**
024 * Experimental neighbor selection that allows an exam to be split
025 * into two if it decreases the number of student conflicts.
026 * <br><br>
027 * An examination split is improving (and is considered) if the weighted
028 * number of student conflicts that will be removed by the split is bigger
029 * than the weight of the splitter criterion {@link ExamSplitter#getWeight()}.
030 *
031 * <br>
032 *
033 * @version ExamTT 1.2 (Examination Timetabling)<br>
034 * Copyright (C) 2008 - 2013 Tomas Muller<br>
035 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
036 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
037 * <br>
038 * This library is free software; you can redistribute it and/or modify
039 * it under the terms of the GNU Lesser General Public License as
040 * published by the Free Software Foundation; either version 3 of the
041 * License, or (at your option) any later version. <br>
042 * <br>
043 * This library is distributed in the hope that it will be useful, but
044 * WITHOUT ANY WARRANTY; without even the implied warranty of
045 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
046 * Lesser General Public License for more details. <br>
047 * <br>
048 * You should have received a copy of the GNU Lesser General Public
049 * License along with this library; if not see
050 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
051 */
052 public class ExamSplitMoves implements NeighbourSelection<Exam, ExamPlacement> {
053 private static Logger sLog = Logger.getLogger(ExamSplitMoves.class);
054 private ExamSplitter iSplitter = null;
055
056 /** Constructor */
057 public ExamSplitMoves(DataProperties properties) {}
058
059 /** Initialization */
060 @Override
061 public void init(Solver<Exam, ExamPlacement> solver) {
062 iSplitter = (ExamSplitter)solver.currentSolution().getModel().getCriterion(ExamSplitter.class);
063 if (iSplitter == null) throw new RuntimeException("ExamSplitter criterion needs to be used as well.");
064 }
065
066 /**
067 * Find best available rooms for a new exam (that is to be split from the given one),
068 * if is is assigned into the given examination period.
069 *
070 * @param exam an exam to be split
071 * @param period a period to be assigned to the new exam
072 * @param examSize size of the new exam (i.e., the number of students that will be moved from the given exam to the new one)
073 * @return best room placement for the given exam and period
074 */
075 public Set<ExamRoomPlacement> findBestAvailableRooms(Exam exam, ExamPeriodPlacement period, int examSize) {
076 if (exam.getMaxRooms() == 0) return new HashSet<ExamRoomPlacement>();
077 double sw = exam.getModel().getCriterion(RoomSizePenalty.class).getWeight();
078 double pw = exam.getModel().getCriterion(RoomPenalty.class).getWeight();
079 loop: for (int nrRooms = 1; nrRooms <= exam.getMaxRooms(); nrRooms++) {
080 HashSet<ExamRoomPlacement> rooms = new HashSet<ExamRoomPlacement>();
081 int size = 0;
082 while (rooms.size() < nrRooms && size < examSize) {
083 int minSize = (examSize - size) / (nrRooms - rooms.size());
084 ExamRoomPlacement best = null;
085 double bestWeight = 0;
086 int bestSize = 0;
087 for (ExamRoomPlacement room : exam.getRoomPlacements()) {
088 if (!room.isAvailable(period.getPeriod()))
089 continue;
090 if (!room.getRoom().getPlacements(period.getPeriod()).isEmpty())
091 continue;
092 if (rooms.contains(room))
093 continue;
094 int s = room.getSize(exam.hasAltSeating());
095 if (s < minSize)
096 break;
097 int p = room.getPenalty(period.getPeriod());
098 double w = pw * p + sw * (s - minSize);
099 double d = 0;
100 if (!rooms.isEmpty()) {
101 for (ExamRoomPlacement r : rooms) {
102 d += r.getDistanceInMeters(room);
103 }
104 w += d / rooms.size();
105 }
106 if (best == null || bestWeight > w) {
107 best = room;
108 bestSize = s;
109 bestWeight = w;
110 }
111 }
112 if (best == null)
113 continue loop;
114 rooms.add(best);
115 size += bestSize;
116 }
117 if (size >= examSize)
118 return rooms;
119 }
120 return null;
121 }
122
123 /**
124 * Find a best split for the given exam. Only improving neighbors are considered.
125 * @param exam an exam to be split
126 * @return best neighbor that will do the split
127 */
128 public ExamSplitNeighbour bestSplit(Exam exam) {
129 ExamSplitNeighbour split = null;
130 ExamPlacement placement = exam.getAssignment();
131 int px = ToolBox.random(exam.getPeriodPlacements().size());
132 for (int p = 0; p < exam.getPeriodPlacements().size(); p++) { // Iterate over possible periods
133 ExamPeriodPlacement period = exam.getPeriodPlacements().get((p + px) % exam.getPeriodPlacements().size());
134 if (placement != null && placement.getPeriod().equals(period)) continue;
135 // Try to create a neighbor
136 ExamSplitNeighbour s = new ExamSplitNeighbour(exam, new ExamPlacement(exam, period, null));
137 if (split == null || s.value() < split.value()) {
138 // If improving, try to find available rooms
139 Set<ExamRoomPlacement> rooms = findBestAvailableRooms(exam, period, s.nrStudents());
140 if (rooms != null) {
141 // Remember as best split
142 s.placement().getRoomPlacements().addAll(rooms);
143 split = s;
144 }
145 }
146 }
147 return split;
148 }
149
150 /**
151 * Select a split (split an exam into two), a merge (merge two split exams back together) or
152 * shuffle operation (move students between two exams that has been split before).
153 */
154 @Override
155 public Neighbour<Exam, ExamPlacement> selectNeighbour(Solution<Exam, ExamPlacement> solution) {
156 // Randomly select an exam
157 Exam exam = ToolBox.random(solution.getModel().assignedVariables());
158
159 // Parent exam (its either the exam itself, or its parent if it has been already split)
160 Exam parent = iSplitter.parent(exam);
161 // Its children (if already split)
162 List<Exam> children = iSplitter.children(parent);
163
164 // Already split -> try shuffle
165 if (children != null && !children.isEmpty()) {
166 ExamShuffleNeighbour shuffle = new ExamShuffleNeighbour(exam);
167 if (shuffle.value() < 0.0) return shuffle;
168 }
169
170 // Can split -> try a split
171 if (iSplitter.canSplit(exam)) {
172 ExamSplitNeighbour split = bestSplit(exam);
173 if (split != null && split.value() < 0.0) return split;
174 }
175
176 // Can merge -> try to merge
177 if (iSplitter.canMerge(exam)) {
178 ExamMergeNeighbour merge = new ExamMergeNeighbour(exam);
179 if (merge.value() < 0.0) return merge;
180 }
181
182 return null;
183 }
184
185 /**
186 * Split an exam into two
187 */
188 protected class ExamSplitNeighbour extends Neighbour<Exam, ExamPlacement> {
189 private Exam iExam;
190 private ExamPlacement iPlacement;
191 private double iValue = 0.0;
192 private int iNrStudents = 0;
193
194 /**
195 * Split an exam into two, assign the new exam into the given placement.
196 * @param exam an exam to be split
197 * @param placement a placement to be assigned to the new exam
198 */
199 public ExamSplitNeighbour(Exam exam, ExamPlacement placement) {
200 iExam = exam;
201 iPlacement = placement;
202
203 // Parent exam (its either the exam itself, or its parent if it has been already split)
204 Exam parent = iSplitter.parent(exam);
205 // Its children (if already split)
206 List<Exam> children = iSplitter.children(parent);
207
208 // Compute improvement
209 // Consider moving all students of the parent exam to the new placement
210 for (ExamStudent student: parent.getStudents()) {
211 double delta = iSplitter.delta(student, parent.getAssignment(), placement);
212 if (delta < 0.0) {
213 iValue += delta;
214 iNrStudents ++;
215 }
216 }
217 // If there already are other children, consider moving students of these children to the
218 // new placement as well
219 if (children != null)
220 for (Exam child: children)
221 for (ExamStudent student: child.getStudents()) {
222 double delta = iSplitter.delta(student, child.getAssignment(), placement);
223 if (delta < 0.0) {
224 iValue += delta;
225 iNrStudents ++;
226 }
227 }
228
229 // Increase the weight by the splitter criterion weight
230 iValue += iSplitter.getWeight();
231 }
232
233 /**
234 * Perform the split.
235 */
236 @Override
237 public void assign(long iteration) {
238 sLog.info("Splitting " + iExam.getName() + " (" + iExam.getAssignment().getName() + ", " + iPlacement.getName() + ", value: " + iValue + ")");
239 iSplitter.split(iExam, iteration, iPlacement);
240 }
241
242 /**
243 * Value of the split. This is the weight of the splitter criterion minus the weighted sum of
244 * all student conflicts that will be removed by the split.
245 */
246 @Override
247 public double value() {
248 return iValue;
249 }
250
251 /**
252 * Number of students that will be moved into the new exam.
253 */
254 public int nrStudents() {
255 return iNrStudents;
256 }
257
258 /**
259 * Exam to be split.
260 */
261 public Exam exam() {
262 return iExam;
263 }
264
265 /**
266 * Placement of the new exam.
267 */
268 public ExamPlacement placement() {
269 return iPlacement;
270 }
271 }
272
273 /**
274 * Merge two exams that have been split before back into one. This moves
275 * the students from the child exam back to its parent and removes the
276 * child exam from the problem.
277 */
278 protected class ExamMergeNeighbour extends Neighbour<Exam, ExamPlacement> {
279 private Exam iExam;
280 private double iValue = 0.0;
281
282 /**
283 * Child exam to be removed.
284 */
285 public ExamMergeNeighbour(Exam exam) {
286 iExam = exam;
287
288 // Parent exam (its either the exam itself, or its parent if it has been already split)
289 Exam parent = iSplitter.parent(exam);
290 // Its children (if already split)
291 List<Exam> children = iSplitter.children(parent);
292
293 // Compute improvement
294 for (ExamStudent student: exam.getStudents()) {
295 // Try to move each student either back to the parent exam or to any of the other
296 // children exams, if there are any
297 double delta = iSplitter.delta(student, exam.getAssignment(), parent.getAssignment());
298 for (Exam child: children) {
299 if (child.equals(exam)) continue;
300 double d = iSplitter.delta(student, exam.getAssignment(), child.getAssignment());
301 if (d < delta) delta = d;
302 }
303 iValue += delta;
304 }
305 // Decrease the weight by the splitter criterion weight
306 iValue -= iSplitter.getWeight();
307 }
308
309 /**
310 * Perform the merge.
311 */
312 @Override
313 public void assign(long iteration) {
314 sLog.info("Mergning " + iExam.getName() + " (" + iExam.getAssignment().getName() + ", value: " + iValue + ")");
315 iSplitter.merge(iExam, iteration);
316 }
317
318 /**
319 * Value of the merge. This is the weighted sum of all student conflicts that will be added by the merge,
320 * minus the weight of the splitter criterion.
321 */
322 @Override
323 public double value() {
324 return iValue;
325 }
326
327 /**
328 * Number of students that will be moved back to the parent exam or to some other child (if there are any).
329 */
330 public int nrStudents() {
331 return iExam.getStudents().size();
332 }
333
334 /**
335 * Exam to be merged.
336 */
337 public Exam exam() {
338 return iExam;
339 }
340 }
341
342 /**
343 * Shuffle students between the parent exam and all of its children. Only swaps
344 * that are decreasing the weighted sum of student conflicts are considered.
345 */
346 protected class ExamShuffleNeighbour extends Neighbour<Exam, ExamPlacement> {
347 private Exam iExam;
348 private double iValue = 0.0;
349
350 /**
351 * Exam to be shuffled.
352 */
353 public ExamShuffleNeighbour(Exam exam) {
354 iExam = exam;
355
356 // Parent exam (its either the exam itself, or its parent if it has been already split)
357 Exam parent = iSplitter.parent(exam);
358 // Its children (if already split)
359 List<Exam> children = iSplitter.children(parent);
360
361 // Compute improvement
362 // Try moving students away from parent
363 for (ExamStudent student: parent.getStudents()) {
364 Double delta = null;
365 for (Exam x: children) {
366 double d = iSplitter.delta(student, parent.getAssignment(), x.getAssignment());
367 if (delta == null || d < delta) delta = d;
368 }
369 if (delta != null && delta < 0) iValue += delta;
370 }
371
372 // Try moving students away from any child
373 for (Exam child: children) {
374 for (ExamStudent student: child.getStudents()) {
375 double delta = iSplitter.delta(student, child.getAssignment(), parent.getAssignment());
376 for (Exam x: children) {
377 if (x.equals(child)) continue;
378 double d = iSplitter.delta(student, child.getAssignment(), x.getAssignment());
379 if (d < delta) delta = d;
380 }
381 if (delta < 0) iValue += delta;
382 }
383 }
384 }
385
386 /**
387 * Perform the shuffle.
388 */
389 @Override
390 public void assign(long iteration) {
391 sLog.info("Shuffling " + iExam.getName() + " (" + iExam.getAssignment().getName() + ", value: " + iValue + ")");
392 iSplitter.shuffle(iExam, iteration);
393 }
394
395 /**
396 * Value of the shuffle. This is the weighted sum of all student conflicts that will be removed by the shuffle.
397 */
398 @Override
399 public double value() {
400 return iValue;
401 }
402
403 /**
404 * Exam to be shuffled.
405 */
406 public Exam exam() {
407 return iExam;
408 }
409 }
410 }