001package net.sf.cpsolver.exam.split; 002 003import java.util.HashSet; 004import java.util.List; 005import java.util.Set; 006 007import net.sf.cpsolver.exam.criteria.RoomPenalty; 008import net.sf.cpsolver.exam.criteria.RoomSizePenalty; 009import net.sf.cpsolver.exam.model.Exam; 010import net.sf.cpsolver.exam.model.ExamPeriodPlacement; 011import net.sf.cpsolver.exam.model.ExamPlacement; 012import net.sf.cpsolver.exam.model.ExamRoomPlacement; 013import net.sf.cpsolver.exam.model.ExamStudent; 014import net.sf.cpsolver.ifs.heuristics.NeighbourSelection; 015import net.sf.cpsolver.ifs.model.Neighbour; 016import net.sf.cpsolver.ifs.solution.Solution; 017import net.sf.cpsolver.ifs.solver.Solver; 018import net.sf.cpsolver.ifs.util.DataProperties; 019import net.sf.cpsolver.ifs.util.ToolBox; 020 021import 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 Tomáš Müller<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 */ 052public 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}