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