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