001package org.cpsolver.exam.neighbours; 002 003import java.util.HashMap; 004import java.util.HashSet; 005import java.util.Map; 006import java.util.Set; 007 008import org.cpsolver.exam.criteria.DistributionPenalty; 009import org.cpsolver.exam.criteria.RoomPenalty; 010import org.cpsolver.exam.criteria.RoomSizePenalty; 011import org.cpsolver.exam.model.Exam; 012import org.cpsolver.exam.model.ExamDistributionConstraint; 013import org.cpsolver.exam.model.ExamModel; 014import org.cpsolver.exam.model.ExamPeriodPlacement; 015import org.cpsolver.exam.model.ExamPlacement; 016import org.cpsolver.exam.model.ExamRoom; 017import org.cpsolver.exam.model.ExamRoomPlacement; 018import org.cpsolver.ifs.assignment.Assignment; 019import org.cpsolver.ifs.heuristics.NeighbourSelection; 020import org.cpsolver.ifs.model.LazySwap; 021import org.cpsolver.ifs.model.Neighbour; 022import org.cpsolver.ifs.solution.Solution; 023import org.cpsolver.ifs.solver.Solver; 024import org.cpsolver.ifs.util.DataProperties; 025import org.cpsolver.ifs.util.ToolBox; 026 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.3 (Examination Timetabling)<br> 038 * Copyright (C) 2013 - 2014 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(Assignment, 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 Assignment<Exam, ExamPlacement> assignment = solution.getAssignment(); 084 Exam x1 = ToolBox.random(model.variables()); 085 ExamPlacement v1 = assignment.getValue(x1); 086 if (v1 == null) return null; 087 int x = ToolBox.random(model.variables().size()); 088 for (int v = 0; v < model.variables().size(); v++) { 089 Exam x2 = model.variables().get((v + x) % (model.variables().size())); 090 ExamPlacement v2 = assignment.getValue(x2); 091 if (x1.equals(x2) || v2 == null) continue; 092 ExamPeriodPlacement p1 = x1.getPeriodPlacement(v2.getPeriod()); 093 ExamPeriodPlacement p2 = x2.getPeriodPlacement(v1.getPeriod()); 094 if (p1 == null || p2 == null || p1.equals(p2)) continue; 095 if (iCheckStudentConflicts && (x1.countStudentConflicts(assignment, p1) > 0 || x2.countStudentConflicts(assignment, p2) > 0)) continue; 096 if (iCheckDistributionConstraints) { 097 Map<Exam, ExamPlacement> placements = new HashMap<Exam, ExamPlacement>(); 098 placements.put(x1, new ExamPlacement(x1, p1, new HashSet<ExamRoomPlacement>())); 099 placements.put(x2, new ExamPlacement(x2, p2, new HashSet<ExamRoomPlacement>())); 100 if (!checkDistributionConstraints(assignment, x1, p1, placements) || !checkDistributionConstraints(assignment, x2, p2, placements)) continue; 101 } 102 Set<ExamPlacement> conflicts = new HashSet<ExamPlacement>(); 103 conflicts.add(v1); conflicts.add(v2); 104 Map<Exam, ExamPlacement> placements = new HashMap<Exam, ExamPlacement>(); 105 Set<ExamRoomPlacement> r1 = findBestAvailableRooms(assignment, x1, p1, conflicts, placements); 106 if (r1 == null) continue; 107 placements.put(x1, new ExamPlacement(x1, p1, r1)); 108 Set<ExamRoomPlacement> r2 = findBestAvailableRooms(assignment, x2, p2, conflicts, placements); 109 if (r2 == null) continue; 110 return new LazySwap<Exam, ExamPlacement>(new ExamPlacement(x1, p1, r1), new ExamPlacement(x2, p2, r2)); 111 } 112 return null; 113 } 114 115 public boolean checkDistributionConstraints(Assignment<Exam, ExamPlacement> assignment, Exam exam, ExamPeriodPlacement period, Map<Exam, ExamPlacement> placements) { 116 for (ExamDistributionConstraint dc : exam.getDistributionConstraints()) { 117 if (!dc.isHard()) 118 continue; 119 boolean before = true; 120 for (Exam other : dc.variables()) { 121 if (other.equals(this)) { 122 before = false; 123 continue; 124 } 125 ExamPlacement placement = (placements.containsKey(other) ? placements.get(other) : assignment.getValue(other)); 126 if (placement == null) continue; 127 if (before) { 128 if (!dc.getDistributionType().isSatisfied(placement.getPeriod(), period.getPeriod())) 129 return false; 130 } else { 131 if (!dc.getDistributionType().isSatisfied(period.getPeriod(), placement.getPeriod())) 132 return false; 133 } 134 } 135 } 136 return true; 137 } 138 139 public boolean checkDistributionConstraints(Assignment<Exam, ExamPlacement> assignment, Exam exam, ExamRoomPlacement room, Set<ExamPlacement> conflictsToIgnore, Map<Exam, ExamPlacement> placements) { 140 for (ExamDistributionConstraint dc : exam.getDistributionConstraints()) { 141 if (!dc.isHard()) 142 continue; 143 for (Exam other : dc.variables()) { 144 if (other.equals(exam)) continue; 145 ExamPlacement placement = (placements.containsKey(other) ? placements.get(other) : assignment.getValue(other)); 146 if (placement == null || conflictsToIgnore.contains(placement)) continue; 147 if (!dc.getDistributionType().isSatisfied(placement, room)) 148 return false; 149 } 150 } 151 return true; 152 } 153 154 public int getDistributionConstraintPenalty(Assignment<Exam, ExamPlacement> assignment, Exam exam, ExamRoomPlacement room, Set<ExamPlacement> conflictsToIgnore, Map<Exam, ExamPlacement> placements) { 155 int penalty = 0; 156 for (ExamDistributionConstraint dc : exam.getDistributionConstraints()) { 157 if (dc.isHard()) continue; 158 for (Exam other : dc.variables()) { 159 if (other.equals(this)) continue; 160 ExamPlacement placement = (placements.containsKey(other) ? placements.get(other) : assignment.getValue(other)); 161 if (placement == null || conflictsToIgnore.contains(placement)) continue; 162 if (!dc.getDistributionType().isSatisfied(placement, room)) 163 penalty += dc.getWeight(); 164 } 165 } 166 return penalty; 167 } 168 169 public Set<ExamRoomPlacement> findBestAvailableRooms(Assignment<Exam, ExamPlacement> assignment, Exam exam, ExamPeriodPlacement period, Set<ExamPlacement> conflictsToIgnore, Map<Exam, ExamPlacement> placements) { 170 if (exam.getMaxRooms() == 0) 171 return new HashSet<ExamRoomPlacement>(); 172 double sw = exam.getModel().getCriterion(RoomSizePenalty.class).getWeight(); 173 double pw = exam.getModel().getCriterion(RoomPenalty.class).getWeight(); 174 double cw = exam.getModel().getCriterion(DistributionPenalty.class).getWeight(); 175 loop: for (int nrRooms = 1; nrRooms <= exam.getMaxRooms(); nrRooms++) { 176 HashSet<ExamRoomPlacement> rooms = new HashSet<ExamRoomPlacement>(); 177 int size = 0; 178 while (rooms.size() < nrRooms && size < exam.getSize()) { 179 int minSize = (exam.getSize() - size) / (nrRooms - rooms.size()); 180 ExamRoomPlacement best = null; 181 double bestWeight = 0; 182 int bestSize = 0; 183 for (ExamRoomPlacement room : exam.getRoomPlacements()) { 184 if (!room.isAvailable(period.getPeriod())) continue; 185 if (rooms.contains(room)) continue; 186 if (!ExamRoom.checkParents(rooms, room)) continue; 187 188 Set<ExamPlacement> conflicts = new HashSet<ExamPlacement>(conflictsToIgnore); 189 room.getRoom().computeConflicts(assignment, exam, period.getPeriod(), conflicts); 190 if (conflicts.size() > conflictsToIgnore.size()) continue; 191 192 if (iCheckDistributionConstraints && !checkDistributionConstraints(assignment, exam, room, conflictsToIgnore, placements)) continue; 193 int s = room.getSize(exam.hasAltSeating()); 194 if (s < minSize) break; 195 int p = room.getPenalty(period.getPeriod()); 196 double w = pw * p + sw * (s - minSize) + cw * getDistributionConstraintPenalty(assignment, exam, room, conflictsToIgnore, placements); 197 double d = 0; 198 if (!rooms.isEmpty()) { 199 for (ExamRoomPlacement r : rooms) { 200 d += r.getDistanceInMeters(room); 201 } 202 w += d / rooms.size(); 203 } 204 if (best == null || bestWeight > w) { 205 best = room; 206 bestSize = s; 207 bestWeight = w; 208 } 209 } 210 if (best == null) 211 continue loop; 212 rooms.add(best); 213 size += bestSize; 214 } 215 if (size >= exam.getSize()) 216 return rooms; 217 } 218 return null; 219 } 220}