001package net.sf.cpsolver.exam.split; 002 003import java.util.ArrayList; 004import java.util.Collection; 005import java.util.HashMap; 006import java.util.Hashtable; 007import java.util.List; 008import java.util.Map; 009import java.util.Set; 010import java.util.TreeSet; 011 012import net.sf.cpsolver.exam.criteria.ExamCriterion; 013import net.sf.cpsolver.exam.criteria.StudentBackToBackConflicts; 014import net.sf.cpsolver.exam.criteria.StudentDirectConflicts; 015import net.sf.cpsolver.exam.criteria.StudentMoreThan2ADayConflicts; 016import net.sf.cpsolver.exam.model.Exam; 017import net.sf.cpsolver.exam.model.ExamPeriod; 018import net.sf.cpsolver.exam.model.ExamPlacement; 019import net.sf.cpsolver.exam.model.ExamRoomPlacement; 020import net.sf.cpsolver.exam.model.ExamStudent; 021import net.sf.cpsolver.ifs.criteria.Criterion; 022import net.sf.cpsolver.ifs.solver.Solver; 023import 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 Tomáš Müller<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 */ 066public 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}