    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}