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    }