001package net.sf.cpsolver.exam.heuristics;
002
003import java.util.ArrayList;
004import java.util.HashSet;
005import java.util.List;
006import java.util.Set;
007import java.util.TreeSet;
008
009import net.sf.cpsolver.exam.model.Exam;
010import net.sf.cpsolver.exam.model.ExamModel;
011import net.sf.cpsolver.exam.model.ExamPeriodPlacement;
012import net.sf.cpsolver.exam.model.ExamPlacement;
013import net.sf.cpsolver.exam.model.ExamRoomPlacement;
014import net.sf.cpsolver.ifs.extension.ConflictStatistics;
015import net.sf.cpsolver.ifs.extension.Extension;
016import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
017import net.sf.cpsolver.ifs.heuristics.ValueSelection;
018import net.sf.cpsolver.ifs.model.Model;
019import net.sf.cpsolver.ifs.model.Neighbour;
020import net.sf.cpsolver.ifs.model.SimpleNeighbour;
021import net.sf.cpsolver.ifs.model.Value;
022import net.sf.cpsolver.ifs.solution.Solution;
023import net.sf.cpsolver.ifs.solver.Solver;
024import net.sf.cpsolver.ifs.util.DataProperties;
025import net.sf.cpsolver.ifs.util.ToolBox;
026
027import 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 Tomáš Müller<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 */
080public 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}