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