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