001 package net.sf.cpsolver.exam.heuristics;
002
003 import java.util.ArrayList;
004 import java.util.HashSet;
005 import java.util.List;
006 import java.util.Set;
007 import java.util.TreeSet;
008
009 import net.sf.cpsolver.exam.model.Exam;
010 import net.sf.cpsolver.exam.model.ExamModel;
011 import net.sf.cpsolver.exam.model.ExamPeriodPlacement;
012 import net.sf.cpsolver.exam.model.ExamPlacement;
013 import net.sf.cpsolver.exam.model.ExamRoomPlacement;
014 import net.sf.cpsolver.ifs.extension.ConflictStatistics;
015 import net.sf.cpsolver.ifs.extension.Extension;
016 import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
017 import net.sf.cpsolver.ifs.heuristics.ValueSelection;
018 import net.sf.cpsolver.ifs.model.Model;
019 import net.sf.cpsolver.ifs.model.Neighbour;
020 import net.sf.cpsolver.ifs.model.SimpleNeighbour;
021 import net.sf.cpsolver.ifs.model.Value;
022 import net.sf.cpsolver.ifs.solution.Solution;
023 import net.sf.cpsolver.ifs.solver.Solver;
024 import net.sf.cpsolver.ifs.util.DataProperties;
025 import net.sf.cpsolver.ifs.util.ToolBox;
026
027 import org.apache.log4j.Logger;
028
029 /**
030 * Tabu search algorithm. <br>
031 * <br>
032 * If used as {@link NeighbourSelection}, the most improving (re)assignment of a
033 * value to a variable is returned (all variables and all their values are
034 * enumerated). If there are more than one of such assignments, one is selected
035 * randomly. A returned assignment can cause unassignment of other existing
036 * assignments. The search is stopped (
037 * {@link ExamTabuSearch#selectNeighbour(Solution)} returns null) after
038 * TabuSearch.MaxIdle idle (not improving) iterations. <br>
039 * <br>
040 * If used as {@link ValueSelection}, the most improving (re)assignment of a
041 * value to a given variable is returned (all values of the given variable are
042 * enumerated). If there are more than one of such assignments, one is selected
043 * randomly. A returned assignment can cause unassignment of other existing
044 * assignments. <br>
045 * <br>
046 * To avoid cycling, a tabu is maintainded during the search. It is the list of
047 * the last n selected values. A selection of a value that is present in the
048 * tabu list is only allowed when it improves the best ever found solution. <br>
049 * <br>
050 * The minimum size of the tabu list is TabuSearch.MinSize, maximum size is
051 * TabuSearch.MaxSize (tabu list is not used when both sizes are zero). The
052 * current size of the tabu list starts at MinSize (and is reset to MinSize
053 * every time a new best solution is found), it is increased by one up to the
054 * MaxSize after TabuSearch.MaxIdle / (MaxSize - MinSize) non-improving
055 * iterations. <br>
056 * <br>
057 * Conflict-based Statistics {@link ConflictStatistics} (CBS) can be used
058 * instead of (or together with) tabu list, when CBS is used as a solver
059 * extension.
060 *
061 * @version ExamTT 1.2 (Examination Timetabling)<br>
062 * Copyright (C) 2008 - 2010 Tomas Muller<br>
063 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
064 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
065 * <br>
066 * This library is free software; you can redistribute it and/or modify
067 * it under the terms of the GNU Lesser General Public License as
068 * published by the Free Software Foundation; either version 3 of the
069 * License, or (at your option) any later version. <br>
070 * <br>
071 * This library is distributed in the hope that it will be useful, but
072 * WITHOUT ANY WARRANTY; without even the implied warranty of
073 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
074 * Lesser General Public License for more details. <br>
075 * <br>
076 * You should have received a copy of the GNU Lesser General Public
077 * License along with this library; if not see
078 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
079 */
080 public class ExamTabuSearch implements NeighbourSelection<Exam, ExamPlacement>, ValueSelection<Exam, ExamPlacement> {
081 private static Logger sLog = Logger.getLogger(ExamTabuSearch.class);
082 private ConflictStatistics<Exam, ExamPlacement> iStat = null;
083
084 private long iFirstIteration = -1;
085 private long iMaxIdleIterations = 10000;
086
087 private int iTabuMinSize = 0;
088 private int iTabuMaxSize = 0;
089 private TabuList iTabu = null;
090
091 private double iConflictWeight = 1000000;
092 private double iValueWeight = 1;
093
094 /**
095 * <ul>
096 * <li>TabuSearch.MaxIdle ... maximum number of idle iterations (default is
097 * 10000)
098 * <li>TabuSearch.MinSize ... minimum size of the tabu list
099 * <li>TabuSearch.MaxSize ... maximum size of the tabu list
100 * <li>Value.ValueWeight ... weight of a value (i.e.,
101 * {@link Value#toDouble()})
102 * <li>Value.ConflictWeight ... weight of a conflicting value (see
103 * {@link Model#conflictValues(Value)}), it is also weighted by the past
104 * occurrences when conflict-based statistics is used
105 * </ul>
106 */
107 public ExamTabuSearch(DataProperties properties) throws Exception {
108 iTabuMinSize = properties.getPropertyInt("TabuSearch.MinSize", iTabuMinSize);
109 iTabuMaxSize = properties.getPropertyInt("TabuSearch.MaxSize", iTabuMaxSize);
110 if (iTabuMaxSize > 0)
111 iTabu = new TabuList(iTabuMinSize);
112 iMaxIdleIterations = properties.getPropertyLong("TabuSearch.MaxIdle", iMaxIdleIterations);
113 iConflictWeight = properties.getPropertyDouble("Value.ConflictWeight", iConflictWeight);
114 iValueWeight = properties.getPropertyDouble("Value.ValueWeight", iValueWeight);
115 }
116
117 /** Initialization */
118 @Override
119 public void init(Solver<Exam, ExamPlacement> solver) {
120 for (Extension<Exam, ExamPlacement> extension : solver.getExtensions()) {
121 if (ConflictStatistics.class.isInstance(extension))
122 iStat = (ConflictStatistics<Exam, ExamPlacement>) extension;
123 }
124 }
125
126 /**
127 * Neighbor selection
128 */
129 @Override
130 public Neighbour<Exam, ExamPlacement> selectNeighbour(Solution<Exam, ExamPlacement> solution) {
131 if (iFirstIteration < 0)
132 iFirstIteration = solution.getIteration();
133 long idle = solution.getIteration() - Math.max(iFirstIteration, solution.getBestIteration());
134 if (idle > iMaxIdleIterations) {
135 sLog.debug(" [tabu] max idle iterations reached");
136 iFirstIteration = -1;
137 if (iTabu != null)
138 iTabu.clear();
139 return null;
140 }
141 if (iTabu != null && iTabuMaxSize > iTabuMinSize) {
142 if (idle == 0) {
143 iTabu.resize(iTabuMinSize);
144 } else if (idle % (iMaxIdleIterations / (iTabuMaxSize - iTabuMinSize)) == 0) {
145 iTabu.resize(Math.min(iTabuMaxSize, iTabu.size() + 1));
146 }
147 }
148
149 boolean acceptConflicts = solution.getModel().getBestUnassignedVariables() > 0;
150 ExamModel model = (ExamModel) solution.getModel();
151 double bestEval = 0.0;
152 List<ExamPlacement> best = null;
153 for (Exam exam : model.variables()) {
154 ExamPlacement assigned = exam.getAssignment();
155 double assignedVal = (assigned == null ? iConflictWeight : iValueWeight * assigned.toDouble());
156 for (ExamPeriodPlacement period : exam.getPeriodPlacements()) {
157 Set<ExamRoomPlacement> rooms = exam.findBestAvailableRooms(period);
158 if (rooms == null)
159 rooms = exam.findRoomsRandom(period, false);
160 if (rooms == null)
161 continue;
162 ExamPlacement value = new ExamPlacement(exam, period, rooms);
163 if (value.equals(assigned))
164 continue;
165 double eval = iValueWeight * value.toDouble() - assignedVal;
166 if (acceptConflicts) {
167 Set<ExamPlacement> conflicts = model.conflictValues(value);
168 for (ExamPlacement conflict : conflicts) {
169 eval -= iValueWeight * conflict.toDouble();
170 eval += iConflictWeight
171 * (1.0 + (iStat == null ? 0.0 : iStat.countRemovals(solution.getIteration(), conflict,
172 value)));
173 }
174 } else {
175 if (model.inConflict(value))
176 continue;
177 }
178 if (iTabu != null && iTabu.contains(exam.getId() + ":" + value.getPeriod().getIndex())) {
179 int un = model.nrUnassignedVariables() - (assigned == null ? 0 : 1);
180 if (un > model.getBestUnassignedVariables())
181 continue;
182 if (un == model.getBestUnassignedVariables()
183 && model.getTotalValue() + eval >= solution.getBestValue())
184 continue;
185 }
186 if (best == null || bestEval > eval) {
187 if (best == null)
188 best = new ArrayList<ExamPlacement>();
189 else
190 best.clear();
191 best.add(value);
192 bestEval = eval;
193 } else if (bestEval == eval) {
194 best.add(value);
195 }
196 }
197 }
198
199 if (best == null) {
200 sLog.debug(" [tabu] --none--");
201 iFirstIteration = -1;
202 if (iTabu != null)
203 iTabu.clear();
204 return null;
205 }
206 ExamPlacement bestVal = ToolBox.random(best);
207
208 if (sLog.isDebugEnabled()) {
209 Set<ExamPlacement> conflicts = model.conflictValues(bestVal);
210 double wconf = (iStat == null ? 0.0 : iStat.countRemovals(solution.getIteration(), conflicts, bestVal));
211 sLog.debug(" [tabu] "
212 + bestVal
213 + " ("
214 + (bestVal.variable().getAssignment() == null ? "" : "was=" + bestVal.variable().getAssignment()
215 + ", ") + "val=" + bestEval
216 + (conflicts.isEmpty() ? "" : ", conf=" + (wconf + conflicts.size()) + "/" + conflicts) + ")");
217 }
218
219 if (iTabu != null)
220 iTabu.add(bestVal.variable().getId() + ":" + bestVal.getPeriod().getIndex());
221
222 return new SimpleNeighbour<Exam, ExamPlacement>(bestVal.variable(), bestVal);
223 }
224
225 /**
226 * Value selection
227 */
228 @Override
229 public ExamPlacement selectValue(Solution<Exam, ExamPlacement> solution, Exam exam) {
230 if (iFirstIteration < 0)
231 iFirstIteration = solution.getIteration();
232 long idle = solution.getIteration() - Math.max(iFirstIteration, solution.getBestIteration());
233 if (idle > iMaxIdleIterations) {
234 sLog.debug(" [tabu] max idle iterations reached");
235 iFirstIteration = -1;
236 if (iTabu != null)
237 iTabu.clear();
238 return null;
239 }
240 if (iTabu != null && iTabuMaxSize > iTabuMinSize) {
241 if (idle == 0) {
242 iTabu.resize(iTabuMinSize);
243 } else if (idle % (iMaxIdleIterations / (iTabuMaxSize - iTabuMinSize)) == 0) {
244 iTabu.resize(Math.min(iTabuMaxSize, iTabu.size() + 1));
245 }
246 }
247
248 ExamModel model = (ExamModel) solution.getModel();
249 double bestEval = 0.0;
250 List<ExamPlacement> best = null;
251
252 ExamPlacement assigned = exam.getAssignment();
253 // double assignedVal =
254 // (assigned==null?-iConflictWeight:iValueWeight*assigned.toDouble());
255 double assignedVal = (assigned == null ? iConflictWeight : iValueWeight * assigned.toDouble());
256 for (ExamPeriodPlacement period : exam.getPeriodPlacements()) {
257 Set<ExamRoomPlacement> rooms = exam.findBestAvailableRooms(period);
258 if (rooms == null)
259 rooms = exam.findRoomsRandom(period, false);
260 if (rooms == null) {
261 sLog.info("Exam " + exam.getName() + " has no rooms for period " + period);
262 continue;
263 }
264 ExamPlacement value = new ExamPlacement(exam, period, rooms);
265 if (value.equals(assigned))
266 continue;
267 Set<ExamPlacement> conflicts = model.conflictValues(value);
268 double eval = iValueWeight * value.toDouble() - assignedVal;
269 for (ExamPlacement conflict : conflicts) {
270 eval -= iValueWeight * conflict.toDouble();
271 eval += iConflictWeight
272 * (1.0 + (iStat == null ? 0.0 : iStat.countRemovals(solution.getIteration(), conflict, value)));
273 }
274 if (iTabu != null && iTabu.contains(exam.getId() + ":" + value.getPeriod().getIndex())) {
275 int un = model.nrUnassignedVariables() - (assigned == null ? 0 : 1);
276 if (un > model.getBestUnassignedVariables())
277 continue;
278 if (un == model.getBestUnassignedVariables() && model.getTotalValue() + eval >= solution.getBestValue())
279 continue;
280 }
281 if (best == null || bestEval > eval) {
282 if (best == null)
283 best = new ArrayList<ExamPlacement>();
284 else
285 best.clear();
286 best.add(value);
287 bestEval = eval;
288 } else if (bestEval == eval) {
289 best.add(value);
290 }
291 }
292
293 if (best == null)
294 return null;
295 ExamPlacement bestVal = ToolBox.random(best);
296
297 if (sLog.isDebugEnabled()) {
298 Set<ExamPlacement> conflicts = model.conflictValues(bestVal);
299 double wconf = (iStat == null ? 0.0 : iStat.countRemovals(solution.getIteration(), conflicts, bestVal));
300 sLog.debug(" [tabu] "
301 + bestVal
302 + " ("
303 + (bestVal.variable().getAssignment() == null ? "" : "was=" + bestVal.variable().getAssignment()
304 + ", ") + "val=" + bestEval
305 + (conflicts.isEmpty() ? "" : ", conf=" + (wconf + conflicts.size()) + "/" + conflicts) + ")");
306 }
307
308 if (iTabu != null)
309 iTabu.add(exam.getId() + ":" + bestVal.getPeriod().getIndex());
310
311 return bestVal;
312 }
313
314 /** Tabu-list */
315 private static class TabuList {
316 private HashSet<TabuItem> iList = new HashSet<TabuItem>();
317 private int iSize;
318 private long iIteration = 0;
319
320 public TabuList(int size) {
321 iSize = size;
322 }
323
324 public Object add(Object object) {
325 if (iSize == 0)
326 return object;
327 if (contains(object)) {
328 iList.remove(new TabuItem(object, 0));
329 iList.add(new TabuItem(object, iIteration++));
330 return null;
331 } else {
332 Object oldest = null;
333 if (iList.size() >= iSize)
334 oldest = removeOldest();
335 iList.add(new TabuItem(object, iIteration++));
336 return oldest;
337 }
338 }
339
340 public void resize(int newSize) {
341 iSize = newSize;
342 while (iList.size() > newSize)
343 removeOldest();
344 }
345
346 public boolean contains(Object object) {
347 return iList.contains(new TabuItem(object, 0));
348 }
349
350 public void clear() {
351 iList.clear();
352 }
353
354 public int size() {
355 return iSize;
356 }
357
358 public Object removeOldest() {
359 TabuItem oldest = null;
360 for (TabuItem element : iList) {
361 if (oldest == null || oldest.getIteration() > element.getIteration())
362 oldest = element;
363 }
364 if (oldest == null)
365 return null;
366 iList.remove(oldest);
367 return oldest.getObject();
368 }
369
370 @Override
371 public String toString() {
372 return new TreeSet<TabuItem>(iList).toString();
373 }
374 }
375
376 /** Tabu item (an item in {@link TabuList}) */
377 private static class TabuItem implements Comparable<TabuItem> {
378 private Object iObject;
379 private long iIteration;
380
381 public TabuItem(Object object, long iteration) {
382 iObject = object;
383 iIteration = iteration;
384 }
385
386 public Object getObject() {
387 return iObject;
388 }
389
390 public long getIteration() {
391 return iIteration;
392 }
393
394 @Override
395 public boolean equals(Object object) {
396 if (object == null || !(object instanceof TabuItem))
397 return false;
398 return getObject().equals(((TabuItem) object).getObject());
399 }
400
401 @Override
402 public int hashCode() {
403 return getObject().hashCode();
404 }
405
406 @Override
407 public int compareTo(TabuItem o) {
408 return Double.compare(getIteration(), o.getIteration());
409 }
410
411 @Override
412 public String toString() {
413 return getObject().toString();
414 }
415 }
416 }