001package net.sf.cpsolver.exam.neighbours; 002 003import java.util.ArrayList; 004import java.util.HashMap; 005import java.util.HashSet; 006import java.util.List; 007import java.util.Map; 008import java.util.Set; 009 010import net.sf.cpsolver.exam.criteria.DistributionPenalty; 011import net.sf.cpsolver.exam.criteria.RoomPenalty; 012import net.sf.cpsolver.exam.criteria.RoomSizePenalty; 013import net.sf.cpsolver.exam.model.Exam; 014import net.sf.cpsolver.exam.model.ExamDistributionConstraint; 015import net.sf.cpsolver.exam.model.ExamModel; 016import net.sf.cpsolver.exam.model.ExamPeriodPlacement; 017import net.sf.cpsolver.exam.model.ExamPlacement; 018import net.sf.cpsolver.exam.model.ExamRoomPlacement; 019import net.sf.cpsolver.exam.model.ExamRoomSharing; 020import net.sf.cpsolver.ifs.heuristics.NeighbourSelection; 021import net.sf.cpsolver.ifs.model.LazySwap; 022import net.sf.cpsolver.ifs.model.Neighbour; 023import net.sf.cpsolver.ifs.solution.Solution; 024import net.sf.cpsolver.ifs.solver.Solver; 025import net.sf.cpsolver.ifs.util.DataProperties; 026import net.sf.cpsolver.ifs.util.ToolBox; 027 028/** 029 * Try to swap a period between two exams. 030 * Two examinations are randomly selected. A new placement is generated by swapping periods of the two exams. 031 * For each exam, the best possible room placement is found. If the two exams are in the same period, it just tries 032 * to change the room assignments by looking for the best available room placement ignoring the existing room assignments 033 * of the two exams. If no conflict results from the swap the assignment is returned. 034 * The following exams of the second exam in the pair are tried for an exam swap otherwise. 035 * <br><br> 036 * 037 * @version ExamTT 1.2 (Examination Timetabling)<br> 038 * Copyright (C) 2013 Tomáš Müller<br> 039 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 040 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 041 * <br> 042 * This library is free software; you can redistribute it and/or modify 043 * it under the terms of the GNU Lesser General Public License as 044 * published by the Free Software Foundation; either version 3 of the 045 * License, or (at your option) any later version. <br> 046 * <br> 047 * This library is distributed in the hope that it will be useful, but 048 * WITHOUT ANY WARRANTY; without even the implied warranty of 049 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 050 * Lesser General Public License for more details. <br> 051 * <br> 052 * You should have received a copy of the GNU Lesser General Public 053 * License along with this library; if not see 054 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 055 */ 056public class ExamPeriodSwapMove implements NeighbourSelection<Exam,ExamPlacement> { 057 private boolean iCheckStudentConflicts = false; 058 private boolean iCheckDistributionConstraints = true; 059 060 /** 061 * Constructor 062 * @param properties problem properties 063 */ 064 public ExamPeriodSwapMove(DataProperties properties) { 065 iCheckStudentConflicts = properties.getPropertyBoolean("ExamPeriodSwapMove.CheckStudentConflicts", iCheckStudentConflicts); 066 iCheckDistributionConstraints = properties.getPropertyBoolean("ExamPeriodSwapMove.CheckDistributionConstraints", iCheckDistributionConstraints); 067 } 068 069 /** 070 * Initialization 071 */ 072 @Override 073 public void init(Solver<Exam,ExamPlacement> solver) {} 074 075 /** 076 * Select an exam randomly, 077 * select an available period randomly (if it is not assigned), 078 * use rooms if possible, select rooms using {@link Exam#findBestAvailableRooms(ExamPeriodPlacement)} if not (exam is unassigned, a room is not available or used). 079 */ 080 @Override 081 public Neighbour<Exam,ExamPlacement> selectNeighbour(Solution<Exam,ExamPlacement> solution) { 082 ExamModel model = (ExamModel)solution.getModel(); 083 Exam x1 = ToolBox.random(model.variables()); 084 if (x1.getAssignment() == null) return null; 085 int x = ToolBox.random(model.variables().size()); 086 for (int v = 0; v < model.variables().size(); v++) { 087 Exam x2 = model.variables().get((v + x) % (model.variables().size())); 088 if (x1.equals(x2) || x2.getAssignment() == null) continue; 089 ExamPeriodPlacement p1 = x1.getPeriodPlacement(x2.getAssignment().getPeriod()); 090 ExamPeriodPlacement p2 = x2.getPeriodPlacement(x1.getAssignment().getPeriod()); 091 if (p1 == null || p2 == null) continue; 092 if (iCheckStudentConflicts && (x1.countStudentConflicts(p1) > 0 || x2.countStudentConflicts(p2) > 0)) continue; 093 if (iCheckDistributionConstraints) { 094 Map<Exam, ExamPlacement> placements = new HashMap<Exam, ExamPlacement>(); 095 placements.put(x1, new ExamPlacement(x1, p1, new HashSet<ExamRoomPlacement>())); 096 placements.put(x2, new ExamPlacement(x2, p2, new HashSet<ExamRoomPlacement>())); 097 if (!checkDistributionConstraints(x1, p1, placements) || !checkDistributionConstraints(x2, p2, placements)) continue; 098 } 099 Set<ExamPlacement> conflicts = new HashSet<ExamPlacement>(); 100 conflicts.add(x1.getAssignment()); conflicts.add(x2.getAssignment()); 101 Map<Exam, ExamPlacement> placements = new HashMap<Exam, ExamPlacement>(); 102 Set<ExamRoomPlacement> r1 = findBestAvailableRooms(x1, p1, conflicts, placements); 103 if (r1 == null) continue; 104 placements.put(x1, new ExamPlacement(x1, p1, r1)); 105 Set<ExamRoomPlacement> r2 = findBestAvailableRooms(x2, p2, conflicts, placements); 106 if (r2 == null) continue; 107 return new LazySwap<Exam, ExamPlacement>(new ExamPlacement(x1, p1, r1), new ExamPlacement(x2, p2, r2)); 108 } 109 return null; 110 } 111 112 public boolean checkDistributionConstraints(Exam exam, ExamPeriodPlacement period, Map<Exam, ExamPlacement> placements) { 113 for (ExamDistributionConstraint dc : exam.getDistributionConstraints()) { 114 if (!dc.isHard()) 115 continue; 116 boolean before = true; 117 for (Exam other : dc.variables()) { 118 if (other.equals(this)) { 119 before = false; 120 continue; 121 } 122 ExamPlacement placement = (placements.containsKey(other) ? placements.get(other) : other.getAssignment()); 123 if (placement == null) continue; 124 switch (dc.getType()) { 125 case ExamDistributionConstraint.sDistSamePeriod: 126 if (period.getIndex() != placement.getPeriod().getIndex()) 127 return false; 128 break; 129 case ExamDistributionConstraint.sDistDifferentPeriod: 130 if (period.getIndex() == placement.getPeriod().getIndex()) 131 return false; 132 break; 133 case ExamDistributionConstraint.sDistPrecedence: 134 if (before) { 135 if (period.getIndex() <= placement.getPeriod().getIndex()) 136 return false; 137 } else { 138 if (period.getIndex() >= placement.getPeriod().getIndex()) 139 return false; 140 } 141 break; 142 case ExamDistributionConstraint.sDistPrecedenceRev: 143 if (before) { 144 if (period.getIndex() >= placement.getPeriod().getIndex()) 145 return false; 146 } else { 147 if (period.getIndex() <= placement.getPeriod().getIndex()) 148 return false; 149 } 150 break; 151 } 152 } 153 } 154 return true; 155 } 156 157 public boolean checkDistributionConstraints(Exam exam, ExamRoomPlacement room, Set<ExamPlacement> conflictsToIgnore, Map<Exam, ExamPlacement> placements) { 158 for (ExamDistributionConstraint dc : exam.getDistributionConstraints()) { 159 if (!dc.isHard()) 160 continue; 161 for (Exam other : dc.variables()) { 162 if (other.equals(exam)) continue; 163 ExamPlacement placement = (placements.containsKey(other) ? placements.get(other) : other.getAssignment()); 164 if (placement == null || conflictsToIgnore.contains(placement)) continue; 165 switch (dc.getType()) { 166 case ExamDistributionConstraint.sDistSameRoom: 167 if (!placement.getRoomPlacements().contains(room)) 168 return false; 169 break; 170 case ExamDistributionConstraint.sDistDifferentRoom: 171 if (placement.getRoomPlacements().contains(room)) 172 return false; 173 break; 174 } 175 } 176 } 177 return true; 178 } 179 180 public int getDistributionConstraintPenalty(Exam exam, ExamRoomPlacement room, Set<ExamPlacement> conflictsToIgnore, Map<Exam, ExamPlacement> placements) { 181 int penalty = 0; 182 for (ExamDistributionConstraint dc : exam.getDistributionConstraints()) { 183 if (dc.isHard()) continue; 184 for (Exam other : dc.variables()) { 185 if (other.equals(this)) continue; 186 ExamPlacement placement = (placements.containsKey(other) ? placements.get(other) : other.getAssignment()); 187 if (placement == null || conflictsToIgnore.contains(placement)) continue; 188 switch (dc.getType()) { 189 case ExamDistributionConstraint.sDistSameRoom: 190 if (!placement.getRoomPlacements().contains(room)) 191 penalty += dc.getWeight(); 192 break; 193 case ExamDistributionConstraint.sDistDifferentRoom: 194 if (placement.getRoomPlacements().contains(room)) 195 penalty += dc.getWeight(); 196 break; 197 } 198 } 199 } 200 return penalty; 201 } 202 203 public Set<ExamRoomPlacement> findBestAvailableRooms(Exam exam, ExamPeriodPlacement period, Set<ExamPlacement> conflictsToIgnore, Map<Exam, ExamPlacement> placements) { 204 if (exam.getMaxRooms() == 0) 205 return new HashSet<ExamRoomPlacement>(); 206 double sw = exam.getModel().getCriterion(RoomSizePenalty.class).getWeight(); 207 double pw = exam.getModel().getCriterion(RoomPenalty.class).getWeight(); 208 double cw = exam.getModel().getCriterion(DistributionPenalty.class).getWeight(); 209 ExamRoomSharing sharing = ((ExamModel)exam.getModel()).getRoomSharing(); 210 loop: for (int nrRooms = 1; nrRooms <= exam.getMaxRooms(); nrRooms++) { 211 HashSet<ExamRoomPlacement> rooms = new HashSet<ExamRoomPlacement>(); 212 int size = 0; 213 while (rooms.size() < nrRooms && size < exam.getSize()) { 214 int minSize = (exam.getSize() - size) / (nrRooms - rooms.size()); 215 ExamRoomPlacement best = null; 216 double bestWeight = 0; 217 int bestSize = 0; 218 for (ExamRoomPlacement room : exam.getRoomPlacements()) { 219 if (!room.isAvailable(period.getPeriod())) continue; 220 if (rooms.contains(room)) continue; 221 222 List<ExamPlacement> overlaps = new ArrayList<ExamPlacement>(); 223 for (ExamPlacement overlap: room.getRoom().getPlacements(period.getPeriod())) 224 if (!conflictsToIgnore.contains(overlap)) overlaps.add(overlap); 225 for (ExamPlacement other: placements.values()) 226 if (other.getPeriod().equals(period.getPeriod())) 227 for (ExamRoomPlacement r: other.getRoomPlacements()) 228 if (r.getRoom().equals(room.getRoom())) { 229 overlaps.add(other); 230 continue; 231 } 232 233 if (nrRooms == 1 && sharing != null) { 234 if (sharing.inConflict(exam, overlaps, room.getRoom())) 235 continue; 236 } else { 237 if (!overlaps.isEmpty()) 238 continue; 239 } 240 if (iCheckDistributionConstraints && !checkDistributionConstraints(exam, room, conflictsToIgnore, placements)) continue; 241 int s = room.getSize(exam.hasAltSeating()); 242 if (s < minSize) break; 243 int p = room.getPenalty(period.getPeriod()); 244 double w = pw * p + sw * (s - minSize) + cw * getDistributionConstraintPenalty(exam, room, conflictsToIgnore, placements); 245 double d = 0; 246 if (!rooms.isEmpty()) { 247 for (ExamRoomPlacement r : rooms) { 248 d += r.getDistanceInMeters(room); 249 } 250 w += d / rooms.size(); 251 } 252 if (best == null || bestWeight > w) { 253 best = room; 254 bestSize = s; 255 bestWeight = w; 256 } 257 } 258 if (best == null) 259 continue loop; 260 rooms.add(best); 261 size += bestSize; 262 } 263 if (size >= exam.getSize()) 264 return rooms; 265 } 266 return null; 267 } 268}