001 package net.sf.cpsolver.exam.heuristics; 002 003 import java.util.ArrayList; 004 import java.util.Collection; 005 import java.util.HashSet; 006 import java.util.HashMap; 007 import java.util.List; 008 import java.util.Set; 009 import java.util.TreeSet; 010 011 import net.sf.cpsolver.exam.model.Exam; 012 import net.sf.cpsolver.exam.model.ExamInstructor; 013 import net.sf.cpsolver.exam.model.ExamModel; 014 import net.sf.cpsolver.exam.model.ExamPeriodPlacement; 015 import net.sf.cpsolver.exam.model.ExamPlacement; 016 import net.sf.cpsolver.exam.model.ExamRoomPlacement; 017 import net.sf.cpsolver.exam.model.ExamStudent; 018 import net.sf.cpsolver.ifs.heuristics.NeighbourSelection; 019 import net.sf.cpsolver.ifs.model.Neighbour; 020 import net.sf.cpsolver.ifs.solution.Solution; 021 import net.sf.cpsolver.ifs.solver.Solver; 022 import net.sf.cpsolver.ifs.util.DataProperties; 023 import net.sf.cpsolver.ifs.util.JProf; 024 import 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 Tomas Muller<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 */ 071 public 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 @Override 143 public Neighbour<Exam, ExamPlacement> selectNeighbour(Solution<Exam, ExamPlacement> solution) { 144 iSolution = solution; 145 ExamModel model = (ExamModel)solution.getModel(); 146 // if (!model.assignedVariables().isEmpty()) return null; 147 final HashMap<Exam, Vertex> vertices = new HashMap<Exam, Vertex>(); 148 for (Exam x: model.variables()) { 149 vertices.put(x, new Vertex(x)); 150 } 151 for (ExamStudent s: model.getStudents()) { 152 for (Exam x: s.variables()) { 153 for (Exam y: s.variables()) { 154 if (!x.equals(y)) { 155 vertices.get(x).neighbors().add(vertices.get(y)); 156 vertices.get(y).neighbors().add(vertices.get(x)); 157 } 158 } 159 } 160 } 161 for (ExamInstructor i: model.getInstructors()) { 162 for (Exam x: i.variables()) { 163 for (Exam y: i.variables()) { 164 if (!x.equals(y)) { 165 vertices.get(x).neighbors().add(vertices.get(y)); 166 vertices.get(y).neighbors().add(vertices.get(x)); 167 } 168 } 169 } 170 } 171 iProgress.setPhase("Graph coloring-based construction", vertices.size()); 172 iProgress.info("Looking for a conflict-free assignment using " + model.getPeriods().size() + " periods."); 173 iT0 = JProf.currentTimeSec(); iTimeLimitReached = false; 174 if (iMode.isGreedy()) { 175 iProgress.info("Using greedy heuristics only (no backtracking)..."); 176 } else if (backTrack(0, (iMode.isRedundant() ? null : new HashSet<Integer>()), vertices.values())) { 177 iProgress.info("Success!"); 178 } else if (iTimeLimitReached) { 179 iProgress.info("There was no conflict-free schedule found during the given time."); 180 } else if (iSolver.isStop()) { 181 iProgress.info("Solver was stopped."); 182 } else { 183 if (iMode.isRedundant()) 184 iProgress.info("There is no conflict-free schedule!"); 185 else 186 iProgress.info("Conflict-free schedule not found."); 187 } 188 if (iMode.isConstraintCheck()) 189 iSolution.restoreBest(); 190 HashSet<Vertex> remaning = new HashSet<Vertex>(); 191 for (Vertex v: vertices.values()) 192 if (v.color() < 0) remaning.add(v); 193 remaining: while (!remaning.isEmpty()) { 194 Vertex vertex = null; 195 for (Vertex v: remaning) 196 if (vertex == null || v.compareTo(vertex) < 0) 197 vertex = v; 198 remaning.remove(vertex); 199 for (int color: vertex.domain()) 200 if (vertex.colorize(color)) continue remaining; 201 } 202 if (!iMode.isConstraintCheck()) { 203 return new Neighbour<Exam, ExamPlacement>() { 204 @Override 205 public void assign(long iteration) { 206 iProgress.info("Using graph coloring solution ..."); 207 for (Vertex vertex: new TreeSet<Vertex>(vertices.values())) { 208 ExamPeriodPlacement period = vertex.period(); 209 if (period == null || !vertex.exam().checkDistributionConstraints(period)) continue; 210 Set<ExamRoomPlacement> rooms = vertex.exam().findBestAvailableRooms(period); 211 if (rooms == null) continue; 212 vertex.exam().assign(iteration, new ExamPlacement(vertex.exam(), period, rooms)); 213 } 214 HashSet<Vertex> unassigned = new HashSet<Vertex>(); 215 for (Vertex vertex: vertices.values()) { 216 if (vertex.exam().getAssignment() == null) { 217 unassigned.add(vertex); 218 vertex.colorize(-1); 219 } 220 } 221 iSolution.saveBest(); 222 iProgress.info("Extending ..."); 223 unassigned: while (!unassigned.isEmpty()) { 224 Vertex vertex = null; 225 for (Vertex v: unassigned) 226 if (vertex == null || v.compareTo(vertex) < 0) 227 vertex = v; 228 unassigned.remove(vertex); 229 for (int color: vertex.domain()) { 230 if (!vertex.colorize(color)) continue; 231 ExamPeriodPlacement period = vertex.period(color); 232 if (period == null || !vertex.exam().checkDistributionConstraints(period)) continue; 233 Set<ExamRoomPlacement> rooms = vertex.exam().findBestAvailableRooms(period); 234 if (rooms == null) continue; 235 vertex.exam().assign(iteration, new ExamPlacement(vertex.exam(), period, rooms)); 236 continue unassigned; 237 } 238 vertex.colorize(-1); 239 } 240 iSolution.saveBest(); 241 iProgress.info("Construction done."); 242 } 243 @Override 244 public double value() { 245 return 0; 246 } 247 }; 248 } 249 return null; 250 } 251 252 /** Internal graph representation -- needed for domain caching */ 253 private class Vertex implements Comparable<Vertex> { 254 private Exam iExam; 255 private List<Vertex> iNeighbors = new ArrayList<Vertex>(); 256 private int iColor = -1; 257 private HashMap<Integer, ExamPeriodPlacement> iDomain = new HashMap<Integer, ExamPeriodPlacement>(); 258 private HashMap<Integer, Vertex> iTaken = new HashMap<Integer, Vertex>(); 259 260 public Vertex(Exam exam) { 261 iExam = exam; 262 for (ExamPeriodPlacement period: exam.getPeriodPlacements()) 263 iDomain.put(period.getIndex(), period); 264 } 265 266 public List<Vertex> neighbors() { return iNeighbors; } 267 268 public Set<Integer> domain() { return iDomain.keySet(); } 269 270 public ExamPeriodPlacement period() { return (iColor < 0 ? null : iDomain.get(iColor)); } 271 272 public ExamPeriodPlacement period(int color) { return (color < 0 ? null : iDomain.get(color)); } 273 274 private boolean neighborColored(Vertex v, int color) { 275 if (!iDomain.containsKey(color)) return true; 276 if (iTaken.get(color) == null) 277 iTaken.put(color, v); 278 return iTaken.size() < iDomain.size(); 279 } 280 281 private void neighborUncolored(Vertex v, int color) { 282 if (!iDomain.containsKey(color)) return; 283 if (v.equals(iTaken.get(color))) { 284 for (Vertex w: neighbors()) { 285 if (w.equals(v)) continue; 286 if (w.color() == color) { 287 iTaken.put(color, w); 288 return; 289 } 290 } 291 iTaken.remove(color); 292 } 293 } 294 295 public int color() { return iColor; } 296 297 public boolean colorize(int color) { 298 if (iColor == color) return true; 299 ExamPlacement placement = null; 300 if (color >= 0) { 301 if (iTaken.get(color) != null || !iDomain.containsKey(color)) 302 return false; 303 if (iMode.isConstraintCheck()) { 304 ExamPeriodPlacement period = iDomain.get(color); 305 if (!iExam.checkDistributionConstraints(period)) return false; 306 Set<ExamRoomPlacement> rooms = iExam.findBestAvailableRooms(period); 307 if (rooms == null) return false; 308 placement = new ExamPlacement(iExam, period, rooms); 309 } 310 } 311 if (iColor >= 0) { 312 for (Vertex v: neighbors()) 313 v.neighborUncolored(this, iColor); 314 } 315 boolean success = true; 316 if (color >= 0) { 317 for (Vertex v: neighbors()) { 318 if (!v.neighborColored(this, color)) { 319 success = false; break; 320 } 321 } 322 } 323 if (success) { 324 iColor = color; 325 if (iMode.isConstraintCheck()) { 326 if (placement != null) 327 iExam.assign(0l, placement); 328 else 329 iExam.unassign(0l); 330 } 331 } else { // undo 332 for (Vertex v: neighbors()) { 333 v.neighborUncolored(this, color); 334 if (iColor >= 0) 335 v.neighborColored(this, iColor); 336 } 337 } 338 return success; 339 } 340 341 public int degree() { 342 return iNeighbors.size(); 343 } 344 345 public int available() { 346 return iDomain.size() - iTaken.size(); 347 } 348 349 public int degreeNotColored() { 350 int ret = 0; 351 for (Vertex v: neighbors()) 352 if (v.color() < 0) ret ++; 353 return ret; 354 } 355 356 public Exam exam() { return iExam; } 357 358 @Override 359 public int compareTo(Vertex v) { 360 if (available() < v.available()) return -1; 361 if (v.available() < available()) return 1; 362 if (degree() > v.degree()) return -1; 363 if (v.degree() > degree()) return 1; 364 if (degreeNotColored() > v.degreeNotColored()) return -1; 365 if (v.degreeNotColored() > degreeNotColored()) return 1; 366 return Double.compare(exam().getId(), v.exam().getId()); 367 } 368 } 369 }