001package net.sf.cpsolver.exam.heuristics; 002 003import java.util.ArrayList; 004import java.util.Collection; 005import java.util.HashSet; 006import java.util.HashMap; 007import java.util.List; 008import java.util.Set; 009import java.util.TreeSet; 010 011import net.sf.cpsolver.exam.model.Exam; 012import net.sf.cpsolver.exam.model.ExamInstructor; 013import net.sf.cpsolver.exam.model.ExamModel; 014import net.sf.cpsolver.exam.model.ExamPeriodPlacement; 015import net.sf.cpsolver.exam.model.ExamPlacement; 016import net.sf.cpsolver.exam.model.ExamRoomPlacement; 017import net.sf.cpsolver.exam.model.ExamStudent; 018import net.sf.cpsolver.ifs.heuristics.NeighbourSelection; 019import net.sf.cpsolver.ifs.model.Neighbour; 020import net.sf.cpsolver.ifs.solution.Solution; 021import net.sf.cpsolver.ifs.solver.Solver; 022import net.sf.cpsolver.ifs.util.DataProperties; 023import net.sf.cpsolver.ifs.util.JProf; 024import net.sf.cpsolver.ifs.util.Progress; 025 026/** 027 * Examination timetabling construction heuristics based on graph vertex coloring. 028 * This approach is trying to find a (direct) conflict-free examination schedule using 029 * a depth-first search, assigning periods to exams in a way that there is not student or 030 * instructor direct conflict. 031 * <br> 032 * <br> 033 * This heuristics works in following modes (defined by Exam.ColoringConstructionMode). 034 * <ul> 035 * <li>Greedy .. all exams are greedily assigned with periods (and best available rooms); 036 * Exams with smallest number of available periods (or highest number of connected exams 037 * if multiple) are assigned first. 038 * <li>ColorOnly .. all exams are assigned with periods using a depth-first search (ignoring 039 * all other constraints), this coloring is then extended to exam placements as much as possible 040 * <li>Irredundant .. other constraints (distributions, rooms) are considered, however, to 041 * speedup the search redundant colorings are avoided -- this may not find a complete solution, 042 * especially when some periods are not swap-able 043 * <li>Full .. all constraints are considered, a complete solution is guaranteed to be found, if 044 * it exists (and enough time is given) 045 * </ul> 046 * <br> 047 * Time to run can be limited using Exam.ColoringConstructionTimeLimit parameter (double precision, 048 * limit is in seconds, defaults to 5 minutes) 049 * <br> 050 * <br> 051 * 052 * @version ExamTT 1.2 (Examination Timetabling)<br> 053 * Copyright (C) 2008 - 2010 Tomáš Müller<br> 054 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 055 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 056 * <br> 057 * This library is free software; you can redistribute it and/or modify 058 * it under the terms of the GNU Lesser General Public License as 059 * published by the Free Software Foundation; either version 3 of the 060 * License, or (at your option) any later version. <br> 061 * <br> 062 * This library is distributed in the hope that it will be useful, but 063 * WITHOUT ANY WARRANTY; without even the implied warranty of 064 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 065 * Lesser General Public License for more details. <br> 066 * <br> 067 * You should have received a copy of the GNU Lesser General Public 068 * License along with this library; if not see 069 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 070 */ 071public class ExamColoringConstruction implements NeighbourSelection<Exam, ExamPlacement> { 072 private Progress iProgress; 073 private double iT0; 074 private double iTimeLimit = 300.0; 075 private boolean iTimeLimitReached = false; 076 private Solution<Exam, ExamPlacement> iSolution = null; 077 private Mode iMode = Mode.Full; 078 private Solver<Exam, ExamPlacement> iSolver; 079 080 private static enum Mode { 081 Greedy(true, false, true), 082 ColorOnly(false, false, false), 083 Irredundant(false, false, false), 084 Full(false, true, true); 085 boolean iGreedy, iRedundant, iConstraintCheck; 086 private Mode(boolean gr, boolean r, boolean ch) { iGreedy = gr; iRedundant = r; iConstraintCheck = ch; } 087 public boolean isGreedy() { return iGreedy; } 088 public boolean isRedundant() { return iRedundant; } 089 public boolean isConstraintCheck() { return iConstraintCheck; } 090 } 091 092 public ExamColoringConstruction(DataProperties config) { 093 iTimeLimit = config.getPropertyDouble("Exam.ColoringConstructionTimeLimit", iTimeLimit); 094 iMode = Mode.valueOf(config.getProperty("Exam.ColoringConstructionMode", iMode.name())); 095 } 096 097 private boolean backTrack(int index, HashSet<Integer> colorsUsedSoFar, Collection<Vertex> vertices) { 098 if (iTimeLimitReached || iSolver.isStop()) return false; 099 if (JProf.currentTimeSec() - iT0 > iTimeLimit) { 100 iTimeLimitReached = true; 101 return false; 102 } 103 if (index == vertices.size()) return true; 104 if (iProgress.getProgress() < index) { 105 iProgress.setProgress(index); 106 if (iMode.isConstraintCheck()) 107 iSolution.saveBest(); 108 } 109 Vertex vertex = null; 110 for (Vertex v: vertices) { 111 if (v.color() >= 0) continue; 112 if (vertex == null || v.compareTo(vertex) < 0) { 113 vertex = v; 114 } 115 } 116 if (colorsUsedSoFar != null) { 117 for (int color: new TreeSet<Integer>(colorsUsedSoFar)) 118 if (vertex.colorize(color) && backTrack(1 + index, colorsUsedSoFar, vertices)) return true; 119 for (int color: vertex.domain()) { 120 if (colorsUsedSoFar.contains(color)) continue; 121 if (vertex.colorize(color)) { 122 colorsUsedSoFar.add(color); 123 if (backTrack(1 + index, colorsUsedSoFar, vertices)) return true; 124 colorsUsedSoFar.remove(color); 125 } 126 break; 127 } 128 } else { 129 for (int color: vertex.domain()) 130 if (vertex.colorize(color) && backTrack(1 + index, colorsUsedSoFar, vertices)) return true; 131 } 132 vertex.colorize(-1); 133 return false; 134 } 135 136 @Override 137 public void init(Solver<Exam, ExamPlacement> solver) { 138 iProgress = Progress.getInstance(solver.currentSolution().getModel()); 139 iSolver = solver; 140 } 141 142 public Set<ExamRoomPlacement> findRooms(Exam exam, ExamPeriodPlacement period) { 143 Set<ExamRoomPlacement> rooms = exam.findBestAvailableRooms(period); 144 if (rooms != null) return rooms; 145 146 rooms = new HashSet<ExamRoomPlacement>(); 147 int size = 0; 148 while (size < exam.getSize()) { 149 ExamRoomPlacement bestRoom = null; int bestSize = 0; 150 for (ExamRoomPlacement r: exam.getRoomPlacements()) { 151 if (!r.isAvailable(period.getPeriod())) continue; 152 if (rooms.contains(r)) continue; 153 if (!r.getRoom().getPlacements(period.getPeriod()).isEmpty()) continue; 154 int s = r.getSize(exam.hasAltSeating()); 155 if (bestRoom == null || s > bestSize) { 156 bestRoom = r; 157 bestSize = s; 158 } 159 } 160 if (bestRoom == null) return rooms; 161 rooms.add(bestRoom); size += bestSize; 162 } 163 164 return rooms; 165 } 166 167 @Override 168 public Neighbour<Exam, ExamPlacement> selectNeighbour(Solution<Exam, ExamPlacement> solution) { 169 iSolution = solution; 170 ExamModel model = (ExamModel)solution.getModel(); 171 // if (!model.assignedVariables().isEmpty()) return null; 172 final HashMap<Exam, Vertex> vertices = new HashMap<Exam, Vertex>(); 173 for (Exam x: model.variables()) { 174 vertices.put(x, new Vertex(x)); 175 } 176 for (ExamStudent s: model.getStudents()) { 177 for (Exam x: s.variables()) { 178 for (Exam y: s.variables()) { 179 if (!x.equals(y)) { 180 vertices.get(x).neighbors().add(vertices.get(y)); 181 vertices.get(y).neighbors().add(vertices.get(x)); 182 } 183 } 184 } 185 } 186 for (ExamInstructor i: model.getInstructors()) { 187 for (Exam x: i.variables()) { 188 for (Exam y: i.variables()) { 189 if (!x.equals(y)) { 190 vertices.get(x).neighbors().add(vertices.get(y)); 191 vertices.get(y).neighbors().add(vertices.get(x)); 192 } 193 } 194 } 195 } 196 iProgress.setPhase("Graph coloring-based construction", vertices.size()); 197 iProgress.info("Looking for a conflict-free assignment using " + model.getPeriods().size() + " periods."); 198 iT0 = JProf.currentTimeSec(); iTimeLimitReached = false; 199 if (iMode.isGreedy()) { 200 iProgress.info("Using greedy heuristics only (no backtracking)..."); 201 } else if (backTrack(0, (iMode.isRedundant() ? null : new HashSet<Integer>()), vertices.values())) { 202 iProgress.info("Success!"); 203 } else if (iTimeLimitReached) { 204 iProgress.info("There was no conflict-free schedule found during the given time."); 205 } else if (iSolver.isStop()) { 206 iProgress.info("Solver was stopped."); 207 } else { 208 if (iMode.isRedundant()) 209 iProgress.info("There is no conflict-free schedule!"); 210 else 211 iProgress.info("Conflict-free schedule not found."); 212 } 213 if (iMode.isConstraintCheck()) 214 iSolution.restoreBest(); 215 HashSet<Vertex> remaning = new HashSet<Vertex>(); 216 for (Vertex v: vertices.values()) 217 if (v.color() < 0) remaning.add(v); 218 remaining: while (!remaning.isEmpty()) { 219 Vertex vertex = null; 220 for (Vertex v: remaning) 221 if (vertex == null || v.compareTo(vertex) < 0) 222 vertex = v; 223 remaning.remove(vertex); 224 for (int color: vertex.domain()) 225 if (vertex.colorize(color)) continue remaining; 226 } 227 if (!iMode.isConstraintCheck()) { 228 return new Neighbour<Exam, ExamPlacement>() { 229 @Override 230 public void assign(long iteration) { 231 iProgress.info("Using graph coloring solution ..."); 232 for (Vertex vertex: new TreeSet<Vertex>(vertices.values())) { 233 ExamPeriodPlacement period = vertex.period(); 234 if (period == null || !vertex.exam().checkDistributionConstraints(period)) continue; 235 Set<ExamRoomPlacement> rooms = findRooms(vertex.exam(), period); 236 if (rooms == null) continue; 237 vertex.exam().assign(iteration, new ExamPlacement(vertex.exam(), period, rooms)); 238 } 239 HashSet<Vertex> unassigned = new HashSet<Vertex>(); 240 for (Vertex vertex: vertices.values()) { 241 if (vertex.exam().getAssignment() == null) { 242 unassigned.add(vertex); 243 vertex.colorize(-1); 244 } 245 } 246 iSolution.saveBest(); 247 iProgress.info("Extending ..."); 248 unassigned: while (!unassigned.isEmpty()) { 249 Vertex vertex = null; 250 for (Vertex v: unassigned) 251 if (vertex == null || v.compareTo(vertex) < 0) 252 vertex = v; 253 unassigned.remove(vertex); 254 for (int color: vertex.domain()) { 255 if (!vertex.colorize(color)) continue; 256 ExamPeriodPlacement period = vertex.period(color); 257 if (period == null || !vertex.exam().checkDistributionConstraints(period)) continue; 258 Set<ExamRoomPlacement> rooms = findRooms(vertex.exam(), period); 259 if (rooms == null) continue; 260 vertex.exam().assign(iteration, new ExamPlacement(vertex.exam(), period, rooms)); 261 continue unassigned; 262 } 263 vertex.colorize(-1); 264 } 265 iSolution.saveBest(); 266 iProgress.info("Construction done."); 267 } 268 @Override 269 public double value() { 270 return 0; 271 } 272 }; 273 } 274 return null; 275 } 276 277 /** Internal graph representation -- needed for domain caching */ 278 private class Vertex implements Comparable<Vertex> { 279 private Exam iExam; 280 private List<Vertex> iNeighbors = new ArrayList<Vertex>(); 281 private int iColor = -1; 282 private HashMap<Integer, ExamPeriodPlacement> iDomain = new HashMap<Integer, ExamPeriodPlacement>(); 283 private HashMap<Integer, Vertex> iTaken = new HashMap<Integer, Vertex>(); 284 285 public Vertex(Exam exam) { 286 iExam = exam; 287 for (ExamPeriodPlacement period: exam.getPeriodPlacements()) 288 iDomain.put(period.getIndex(), period); 289 } 290 291 public List<Vertex> neighbors() { return iNeighbors; } 292 293 public Set<Integer> domain() { return iDomain.keySet(); } 294 295 public ExamPeriodPlacement period() { return (iColor < 0 ? null : iDomain.get(iColor)); } 296 297 public ExamPeriodPlacement period(int color) { return (color < 0 ? null : iDomain.get(color)); } 298 299 private boolean neighborColored(Vertex v, int color) { 300 if (!iDomain.containsKey(color)) return true; 301 if (iTaken.get(color) == null) 302 iTaken.put(color, v); 303 return iTaken.size() < iDomain.size(); 304 } 305 306 private void neighborUncolored(Vertex v, int color) { 307 if (!iDomain.containsKey(color)) return; 308 if (v.equals(iTaken.get(color))) { 309 for (Vertex w: neighbors()) { 310 if (w.equals(v)) continue; 311 if (w.color() == color) { 312 iTaken.put(color, w); 313 return; 314 } 315 } 316 iTaken.remove(color); 317 } 318 } 319 320 public int color() { return iColor; } 321 322 public boolean colorize(int color) { 323 if (iColor == color) return true; 324 ExamPlacement placement = null; 325 if (color >= 0) { 326 if (iTaken.get(color) != null || !iDomain.containsKey(color)) 327 return false; 328 if (iMode.isConstraintCheck()) { 329 ExamPeriodPlacement period = iDomain.get(color); 330 if (!iExam.checkDistributionConstraints(period)) return false; 331 Set<ExamRoomPlacement> rooms = findRooms(iExam, period); 332 if (rooms == null) return false; 333 placement = new ExamPlacement(iExam, period, rooms); 334 } 335 } 336 if (iColor >= 0) { 337 for (Vertex v: neighbors()) 338 v.neighborUncolored(this, iColor); 339 } 340 boolean success = true; 341 if (color >= 0) { 342 for (Vertex v: neighbors()) { 343 if (!v.neighborColored(this, color)) { 344 success = false; break; 345 } 346 } 347 } 348 if (success) { 349 iColor = color; 350 if (iMode.isConstraintCheck()) { 351 if (placement != null) 352 iExam.assign(0l, placement); 353 else 354 iExam.unassign(0l); 355 } 356 } else { // undo 357 for (Vertex v: neighbors()) { 358 v.neighborUncolored(this, color); 359 if (iColor >= 0) 360 v.neighborColored(this, iColor); 361 } 362 } 363 return success; 364 } 365 366 public int degree() { 367 return iNeighbors.size(); 368 } 369 370 public int available() { 371 return iDomain.size() - iTaken.size(); 372 } 373 374 public int degreeNotColored() { 375 int ret = 0; 376 for (Vertex v: neighbors()) 377 if (v.color() < 0) ret ++; 378 return ret; 379 } 380 381 public Exam exam() { return iExam; } 382 383 @Override 384 public int compareTo(Vertex v) { 385 if (available() < v.available()) return -1; 386 if (v.available() < available()) return 1; 387 if (degree() > v.degree()) return -1; 388 if (v.degree() > degree()) return 1; 389 if (degreeNotColored() > v.degreeNotColored()) return -1; 390 if (v.degreeNotColored() > degreeNotColored()) return 1; 391 return Double.compare(exam().getId(), v.exam().getId()); 392 } 393 } 394}