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