    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}