001 package net.sf.cpsolver.exam.split;
002
003 import java.util.ArrayList;
004 import java.util.Collection;
005 import java.util.HashMap;
006 import java.util.Hashtable;
007 import java.util.List;
008 import java.util.Map;
009 import java.util.Set;
010 import java.util.TreeSet;
011
012 import net.sf.cpsolver.exam.criteria.ExamCriterion;
013 import net.sf.cpsolver.exam.criteria.StudentBackToBackConflicts;
014 import net.sf.cpsolver.exam.criteria.StudentDirectConflicts;
015 import net.sf.cpsolver.exam.criteria.StudentMoreThan2ADayConflicts;
016 import net.sf.cpsolver.exam.model.Exam;
017 import net.sf.cpsolver.exam.model.ExamPeriod;
018 import net.sf.cpsolver.exam.model.ExamPlacement;
019 import net.sf.cpsolver.exam.model.ExamRoomPlacement;
020 import net.sf.cpsolver.exam.model.ExamStudent;
021 import net.sf.cpsolver.ifs.criteria.Criterion;
022 import net.sf.cpsolver.ifs.solver.Solver;
023 import net.sf.cpsolver.ifs.util.DataProperties;
024
025 /**
026 * Experimental criterion that allows an exam to be split
027 * into two if it decreases the number of student conflicts.
028 * <br><br>
029 * An examination split is improving (and is considered) if the weighted
030 * number of student conflicts that will be removed by the split is bigger
031 * than the weight of the splitter criterion {@link ExamSplitter#getWeight()}.
032 * <br><br>
033 * To enable examination splitting, following parameters needs to be set:
034 * <ul>
035 * <li>HillClimber.AdditionalNeighbours=net.sf.cpsolver.exam.split.ExamSplitMoves
036 * <li>GreatDeluge.AdditionalNeighbours=net.sf.cpsolver.exam.split.ExamSplitMoves
037 * <li>Exams.AdditionalCriteria=net.sf.cpsolver.exam.split.ExamSplitter
038 * <li>Exams.ExamSplitWeight=500
039 * </ul>
040 * The Exams.ExamSplitWeight represents the weight of a split. For instance, to
041 * allow only splits that decrease the number of student direct conflicts,
042 * half of the weight of a direct student conflict is a good value for this
043 * weight.
044 *
045 * <br>
046 *
047 * @version ExamTT 1.2 (Examination Timetabling)<br>
048 * Copyright (C) 2008 - 2013 Tomas Muller<br>
049 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
050 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
051 * <br>
052 * This library is free software; you can redistribute it and/or modify
053 * it under the terms of the GNU Lesser General Public License as
054 * published by the Free Software Foundation; either version 3 of the
055 * License, or (at your option) any later version. <br>
056 * <br>
057 * This library is distributed in the hope that it will be useful, but
058 * WITHOUT ANY WARRANTY; without even the implied warranty of
059 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
060 * Lesser General Public License for more details. <br>
061 * <br>
062 * You should have received a copy of the GNU Lesser General Public
063 * License along with this library; if not see
064 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
065 */
066 public class ExamSplitter extends ExamCriterion {
067 private long iLastSplitId = 0;
068 private Map<Exam, List<Exam>> iChildren = new HashMap<Exam, List<Exam>>();
069 private Map<Exam, Exam> iParent = new HashMap<Exam, Exam>();
070 private Criterion<Exam, ExamPlacement> iStudentDirectConflicts, iStudentMoreThan2ADayConflicts, iStudentBackToBackConflicts;
071
072 private Map<Exam, List<ExamPlacement>> iBestSplit = null;
073
074 /** Examination splitter criterion. */
075 public ExamSplitter() {
076 iValueUpdateType = ValueUpdateType.NoUpdate;
077 }
078
079 /** Initialization */
080 @Override
081 public boolean init(Solver<Exam, ExamPlacement> solver) {
082 boolean ret = super.init(solver);
083 iStudentDirectConflicts = solver.currentSolution().getModel().getCriterion(StudentDirectConflicts.class);
084 iStudentMoreThan2ADayConflicts = solver.currentSolution().getModel().getCriterion(StudentMoreThan2ADayConflicts.class);
085 iStudentBackToBackConflicts = solver.currentSolution().getModel().getCriterion(StudentBackToBackConflicts.class);
086 return ret;
087 }
088
089 /** Returns Exams.ExamSplitWeight */
090 @Override
091 public String getWeightName() {
092 return "Exams.ExamSplitWeight";
093 }
094
095 /** Returns examSplitWeight */
096 @Override
097 public String getXmlWeightName() {
098 return "examSplitWeight";
099 }
100
101 /** Returns half of a student direct conflict weight */
102 @Override
103 public double getWeightDefault(DataProperties config) {
104 return (iStudentDirectConflicts != null ? iStudentDirectConflicts.getWeight() / 2 : 500.0);
105 }
106
107 private boolean isDayBreakBackToBack() {
108 return ((StudentBackToBackConflicts)iStudentBackToBackConflicts).isDayBreakBackToBack();
109 }
110
111 /** True, if an exam can be split */
112 public boolean canSplit(Exam exam) {
113 if (iParent.containsKey(exam)) return false; // already split
114 return true;
115 }
116
117 /**
118 * Parent of an exam that has been split.
119 * @param exam an exam in question
120 * @return parent exam if the exam has been split, or the exam itself otherwise (each non-split exam is its own parent)
121 */
122 public Exam parent(Exam exam) {
123 return (iParent.containsKey(exam) ? iParent.get(exam) : exam);
124 }
125
126 /**
127 * Children exams of an exam that has been split. These are all the exams that the parent exam has been split into.
128 * @param parent an exam in question
129 * @return all children exams, or null of the exam has not been split yet
130 */
131 public List<Exam> children(Exam parent) {
132 return iChildren.get(parent);
133 }
134
135 /**
136 * Split an exam
137 * @param parent an exam to be split
138 * @param iteration solver iteration
139 * @param placement placement of the new exam
140 * @return new exam assigned to the given placement with students moved into it; null if the given exam cannot be split
141 */
142 public Exam split(Exam parent, long iteration, ExamPlacement placement) {
143 if (!canSplit(parent)) return null;
144
145 // Create the child exam
146 Exam child = new Exam(--iLastSplitId, parent.getName(), parent.getLength(), parent.hasAltSeating(), parent.getMaxRooms(), parent.getMinSize(), parent.getPeriodPlacements(), parent.getRoomPlacements());
147 child.setSizeOverride(parent.getSizeOverride());
148 child.setPrintOffset(parent.getPrintOffset());
149 child.setAveragePeriod(parent.getAveragePeriod());
150 child.getOwners().addAll(parent.getOwners());
151
152 // Update the parent and children structures
153 iParent.put(child, parent);
154 List<Exam> children = iChildren.get(parent);
155 if (children == null) {
156 children = new ArrayList<Exam>();
157 iChildren.put(parent, children);
158 }
159 children.add(child);
160 iValue += 1.0;
161
162 // Add into model
163 parent.getModel().addVariable(child);
164 for (ExamRoomPlacement room : child.getRoomPlacements())
165 room.getRoom().addVariable(child);
166 if (placement != null) child.assign(iteration, new ExamPlacement(child, placement.getPeriodPlacement(), placement.getRoomPlacements()));
167
168
169 // Shuffle students between parent exam and its children
170 shuffle(parent, iteration);
171
172 // Return the new exam
173 return child;
174 }
175
176 /** True, if the given exam can be merged (it has been split) */
177 public boolean canMerge(Exam exam) {
178 if (!iParent.containsKey(exam)) return false; // not split
179 return true;
180 }
181
182 /**
183 * Merge an exam
184 * @param child an exam to be merged
185 * @param iteration solver iteration
186 * @return parent exam of the exam that has been deleted; null if the given exam cannot be merged
187 */
188 public Exam merge(Exam child, long iteration) {
189 if (!canMerge(child)) return null;
190
191 // Update the parent and children structures
192 Exam parent = iParent.get(child);
193 iParent.remove(child);
194 List<Exam> children = iChildren.get(parent);
195 children.remove(child);
196 iValue -= 1.0;
197
198 // Unassign parent and the given exam
199 ExamPlacement parentPlacement = parent.getAssignment();
200 if (parentPlacement != null) parent.unassign(iteration);
201 if (child.getAssignment() != null) child.unassign(iteration);
202
203 // Move students back from the given exam
204 for (ExamStudent student: new ArrayList<ExamStudent>(child.getStudents())) {
205 student.removeVariable(child);
206 student.addVariable(parent);
207 }
208
209 // Remove the given exam from the model
210 for (ExamRoomPlacement room : child.getRoomPlacements())
211 room.getRoom().removeVariable(child);
212 parent.getModel().removeVariable(child);
213
214 // Assign parent exam back
215 if (parentPlacement != null) parent.assign(iteration, parentPlacement);
216
217
218 // Shuffle students between parent exam and its remaining children
219 shuffle(parent, iteration);
220
221 // Return parent exam
222 return parent;
223 }
224
225 /**
226 * Difference in the total weighted student conflicts (including {@link StudentDirectConflicts},
227 * {@link StudentMoreThan2ADayConflicts}, and {@link StudentBackToBackConflicts}) if a student
228 * is moved from an exam with one placement into an exam with another placement.
229 * @param student a student in question
230 * @param oldPlacement placement of the exam in which the student is now
231 * @param newPlacement placement of the exam into which the student would be moved
232 * @return difference in the student conflict weight
233 */
234 public double delta(ExamStudent student, ExamPlacement oldPlacement, ExamPlacement newPlacement) {
235 double delta = 0;
236
237 // Weights of removing student form the old placement
238 if (oldPlacement != null) {
239 Exam exam = oldPlacement.variable();
240 ExamPeriod period = oldPlacement.getPeriod();
241 Set<Exam> examsThisPeriod = student.getExams(period);
242 if (examsThisPeriod.size() > (examsThisPeriod.contains(exam) ? 1 : 0))
243 delta -= iStudentDirectConflicts.getWeight(); // will remove a direct conflict
244 ExamPeriod prev = period.prev();
245 if (prev != null && (prev.getDay() == period.getDay() || isDayBreakBackToBack())) {
246 Set<Exam> examsPrevPeriod = student.getExams(prev);
247 if (examsPrevPeriod.size() > (examsPrevPeriod.contains(exam) ? 1 : 0))
248 delta -= iStudentBackToBackConflicts.getWeight(); // will remove a back-to-back conflict
249 }
250 ExamPeriod next = period.next();
251 if (next != null && (next.getDay() == period.getDay() || isDayBreakBackToBack())) {
252 Set<Exam> examsNextPeriod = student.getExams(next);
253 if (examsNextPeriod.size() > (examsNextPeriod.contains(exam) ? 1 : 0))
254 delta -= iStudentBackToBackConflicts.getWeight(); // will remove a back-to-back conflict
255 }
256 Set<Exam> examsInADay = student.getExamsADay(period);
257 if (examsInADay.size() > (examsInADay.contains(exam) ? 3 : 2))
258 delta -= iStudentMoreThan2ADayConflicts.getWeight(); // will remove a more than 2 on a day conflict
259 }
260
261 // Weights of moving student into the new placement
262 if (newPlacement != null) {
263 Exam exam = newPlacement.variable();
264 ExamPeriod period = newPlacement.getPeriod();
265 Set<Exam> examsThisPeriod = student.getExams(period);
266 if (examsThisPeriod.size() > (examsThisPeriod.contains(exam) ? 1 : 0))
267 delta += iStudentDirectConflicts.getWeight(); // will add a direct conflict
268 ExamPeriod prev = period.prev();
269 if (prev != null && (prev.getDay() == period.getDay() || isDayBreakBackToBack())) {
270 Set<Exam> examsPrevPeriod = student.getExams(prev);
271 if (examsPrevPeriod.size() > (examsPrevPeriod.contains(exam) ? 1 : 0))
272 delta += iStudentBackToBackConflicts.getWeight(); // will add a back-to-back conflict
273 }
274 ExamPeriod next = period.next();
275 if (next != null && (next.getDay() == period.getDay() || isDayBreakBackToBack())) {
276 Set<Exam> examsNextPeriod = student.getExams(next);
277 if (examsNextPeriod.size() > (examsNextPeriod.contains(exam) ? 1 : 0))
278 delta += iStudentBackToBackConflicts.getWeight(); // will add a back-to-back conflict
279 }
280 Set<Exam> examsInADay = student.getExamsADay(period);
281 if (examsInADay.size() > (examsInADay.contains(exam) ? 3 : 2))
282 delta += iStudentMoreThan2ADayConflicts.getWeight(); // will add a more than 2 on a day conflict
283 }
284
285 return delta;
286 }
287
288 /**
289 * Shuffle students between the given exam and all the other exams in the split (if there are any).
290 * Only moves between exams that improve {@link ExamSplitter#delta(ExamStudent, ExamPlacement, ExamPlacement)} are
291 * considered.
292 * @param exam an exam in question
293 * @param iteration solver iteration
294 */
295 public void shuffle(Exam exam, long iteration) {
296 // Parent exam (its either the exam itself, or its parent if it has been already split)
297 Exam parent = (iParent.containsKey(exam) ? iParent.get(exam) : exam);
298 // Its children (if already split)
299 List<Exam> children = iChildren.get(parent);
300
301 if (children != null && !children.isEmpty()) {
302 // Unassign all involved exams
303 Map<Exam, ExamPlacement> assignments = new HashMap<Exam, ExamPlacement>();
304 if (parent.getAssignment() != null) {
305 assignments.put(parent, parent.getAssignment());
306 parent.unassign(iteration);
307 }
308 for (Exam child: children) {
309 if (child.getAssignment() != null) {
310 assignments.put(child, child.getAssignment());
311 child.unassign(iteration);
312 }
313 }
314
315 // Move away from parent
316 for (ExamStudent student: new ArrayList<ExamStudent>(parent.getStudents())) {
317 Exam child = null; double delta = 0;
318 for (Exam x: children) {
319 double d = delta(student, assignments.get(parent), assignments.get(x));
320 if (child == null || d < delta) {
321 delta = d; child = x;
322 }
323 }
324 if (child != null && delta < 0) {
325 student.removeVariable(parent);
326 student.addVariable(child);
327 }
328 }
329
330 // Move students away from a child
331 for (Exam child: children) {
332 for (ExamStudent student: new ArrayList<ExamStudent>(child.getStudents())) {
333 Exam other = parent; double delta = delta(student, assignments.get(child), assignments.get(parent));
334 for (Exam x: children) {
335 if (x.equals(child)) continue;
336 double d = delta(student, assignments.get(child), assignments.get(x));
337 if (d < delta) {
338 delta = d; other = x;
339 }
340 }
341 if (other != null && delta < 0) {
342 student.removeVariable(child);
343 student.addVariable(other);
344 }
345 }
346 }
347
348 // Assign everything back
349 ExamPlacement parentPlacement = assignments.get(parent);
350 if (parentPlacement != null) parent.assign(iteration, parentPlacement);
351 for (Exam child: children) {
352 ExamPlacement placement = assignments.get(child);
353 if (placement != null) child.assign(iteration, placement);
354 }
355 }
356 }
357
358 /** Not used */
359 @Override
360 public double getValue(ExamPlacement value, Set<ExamPlacement> conflicts) {
361 return 0.0;
362 }
363
364 /** Not used */
365 @Override
366 public double[] getBounds(Collection<Exam> exams) {
367 return new double[] { 0.0, 0.0 };
368 }
369
370 @Override
371 public String toString() {
372 return "XX:" + sDoubleFormat.format(getValue());
373 }
374
375 /** Lists the split */
376 @Override
377 public void getInfo(Map<String, String> info) {
378 if (!iChildren.isEmpty()) {
379 int parents = 0;
380 String split = "";
381 for (Exam parent: new TreeSet<Exam>(iChildren.keySet())) {
382 List<Exam> children = iChildren.get(parent);
383 if (children.isEmpty()) continue;
384 split += "\n ";
385 parents ++;
386 split += parent.getName() + ": " + parent.getStudents().size() + " (" + (parent.getAssignment() == null ? "N/A" : parent.getAssignment().getPeriod()) + ")";
387 for (Exam child: children)
388 split += " + " + child.getStudents().size() + " (" + (child.getAssignment() == null ? "N/A" : child.getAssignment().getPeriod()) + ")";
389 }
390 if (parents > 0)
391 info.put("Examination Splits", parents + split);
392 }
393 }
394
395 /** Best solution was saved, remember the current splits */
396 @Override
397 public void bestSaved() {
398 super.bestSaved();
399
400 if (iBestSplit == null)
401 iBestSplit = new Hashtable<Exam, List<ExamPlacement>>();
402 else
403 iBestSplit.clear();
404
405 for (Map.Entry<Exam, List<Exam>> entry: iChildren.entrySet()) {
406 Exam parent = entry.getKey();
407 List<ExamPlacement> placements = new ArrayList<ExamPlacement>();
408 for (Exam child: entry.getValue()) {
409 if (child.getAssignment() != null)
410 placements.add(child.getAssignment());
411 }
412 if (!placements.isEmpty())
413 iBestSplit.put(parent, placements);
414 }
415 }
416
417 /** Best solution was restored, change the splits back to what it was in the best solution */
418 @Override
419 public void bestRestored() {
420 super.bestRestored();
421
422 // Merge those that are not split
423 for (Exam parent: new ArrayList<Exam>(iChildren.keySet())) {
424 List<Exam> children = new ArrayList<Exam>(iChildren.get(parent));
425 List<ExamPlacement> placements = iBestSplit.get(parent);
426 for (int i = (placements == null ? 0 : placements.size()); i < children.size(); i++)
427 merge(children.get(i), 0);
428 }
429
430 // Assign best placements to all children, create children if needed
431 iValue = 0;
432 for (Exam parent: iBestSplit.keySet()) {
433 List<ExamPlacement> placements = iBestSplit.get(parent);
434 for (int i = 0; i < placements.size(); i++) {
435 List<Exam> children = iChildren.get(parent);
436 if (children == null || children.size() <= i) { // create a child if needed
437 split(parent, 0, placements.get(i));
438 } else { // otherwise, just assign the placement
439 children.get(i).assign(0, new ExamPlacement(children.get(i), placements.get(i).getPeriodPlacement(), placements.get(i).getRoomPlacements()));
440 }
441 }
442 iValue += placements.size();
443 }
444 }
445 }