    001package org.cpsolver.exam.heuristics;
    002
    003import org.apache.log4j.Logger;
    004import org.cpsolver.exam.model.Exam;
    005import org.cpsolver.exam.model.ExamPlacement;
    006import org.cpsolver.exam.neighbours.ExamRandomMove;
    007import org.cpsolver.exam.neighbours.ExamRoomMove;
    008import org.cpsolver.exam.neighbours.ExamTimeMove;
    009import org.cpsolver.ifs.algorithms.GreatDeluge;
    010import org.cpsolver.ifs.algorithms.HillClimber;
    011import org.cpsolver.ifs.algorithms.SimulatedAnnealing;
    012import org.cpsolver.ifs.assignment.Assignment;
    013import org.cpsolver.ifs.assignment.context.AssignmentContext;
    014import org.cpsolver.ifs.assignment.context.NeighbourSelectionWithContext;
    015import org.cpsolver.ifs.heuristics.StandardNeighbourSelection;
    016import org.cpsolver.ifs.model.Neighbour;
    017import org.cpsolver.ifs.solution.Solution;
    018import org.cpsolver.ifs.solver.Solver;
    019import org.cpsolver.ifs.termination.TerminationCondition;
    020import org.cpsolver.ifs.util.Callback;
    021import org.cpsolver.ifs.util.DataProperties;
    022import org.cpsolver.ifs.util.Progress;
    023
    024
    025/**
    026 * Examination timetabling neighbour selection. <br>
    027 * <br>
    028 * It consists of the following three phases:
    029 * <ul>
    030 * <li>Construction phase ({@link ExamConstruction} until all exams are
    031 * assigned)
    032 * <li>Hill-climbing phase ({@link HillClimber} until the given number if
    033 * idle iterations)
    034 * <li>Simulated annealing phase ({@link SimulatedAnnealing} until timeout
    035 * is reached)
    036 * <ul>
    037 * <li>Or great deluge phase (when Exam.GreatDeluge is true,
    038 * {@link GreatDeluge} until timeout is reached)
    039 * </ul>
    040 * <li>At the end (when {@link TerminationCondition#canContinue(Solution)} is
    041 * false), the search is finished with one sweep of final phase (
    042 * {@link HillClimber} until the given number if idle iterations).
    043 * </ul>
    044 * <br>
    045 * <br>
    046 *
    047 * @version ExamTT 1.3 (Examination Timetabling)<br>
    048 *          Copyright (C) 2008 - 2014 Tomáš Müller<br>
    049 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    050 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    051 * <br>
    052 *          This library is free software; you can redistribute it and/or modify
    053 *          it under the terms of the GNU Lesser General Public License as
    054 *          published by the Free Software Foundation; either version 3 of the
    055 *          License, or (at your option) any later version. <br>
    056 * <br>
    057 *          This library is distributed in the hope that it will be useful, but
    058 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    059 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    060 *          Lesser General Public License for more details. <br>
    061 * <br>
    062 *          You should have received a copy of the GNU Lesser General Public
    063 *          License along with this library; if not see
    064 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    065 */
    066public class ExamNeighbourSelection extends NeighbourSelectionWithContext<Exam, ExamPlacement, ExamNeighbourSelection.Context> implements TerminationCondition<Exam, ExamPlacement> {
    067    private static Logger sLog = Logger.getLogger(ExamNeighbourSelection.class);
    068    private ExamColoringConstruction iColor = null;
    069    private ExamConstruction iCon = null;
    070    private StandardNeighbourSelection<Exam, ExamPlacement> iStd = null;
    071    private SimulatedAnnealing<Exam, ExamPlacement> iSA = null;
    072    private HillClimber<Exam, ExamPlacement> iHC = null;
    073    private HillClimber<Exam, ExamPlacement> iFin = null;
    074    private GreatDeluge<Exam, ExamPlacement> iGD = null;
    075    private boolean iUseGD = false;
    076    private Progress iProgress = null;
    077    private Callback iFinalPhaseFinished = null;
    078    private TerminationCondition<Exam, ExamPlacement> iTerm = null;
    079    private boolean iFinalPhase = false;
    080
    081    /**
    082     * Constructor
    083     *
    084     * @param properties
    085     *            problem properties
    086     */
    087    public ExamNeighbourSelection(DataProperties properties) {
    088        if (properties.getPropertyBoolean("Exam.ColoringConstruction", false))
    089            iColor = new ExamColoringConstruction(properties);
    090        iCon = new ExamConstruction(properties);
    091        try {
    092            iStd = new StandardNeighbourSelection<Exam, ExamPlacement>(properties);
    093            iStd.setVariableSelection(new ExamUnassignedVariableSelection(properties));
    094            iStd.setValueSelection(new ExamTabuSearch(properties));
    095        } catch (Exception e) {
    096            sLog.error("Unable to initialize standard selection, reason: " + e.getMessage(), e);
    097            iStd = null;
    098        }
    099        properties.setProperty("SimulatedAnnealing.Neighbours", ExamRandomMove.class.getName() + ";" + ExamRoomMove.class.getName() + ";" + ExamTimeMove.class.getName());
    100        iSA = new SimulatedAnnealing<Exam, ExamPlacement>(properties);
    101        properties.setProperty("HillClimber.Neighbours", ExamRandomMove.class.getName() + ";" + ExamRoomMove.class.getName() + ";" + ExamTimeMove.class.getName());
    102        iHC = new HillClimber<Exam, ExamPlacement>(properties);
    103        iFin = new HillClimber<Exam, ExamPlacement>(properties); iFin.setPhase("Finalization");
    104        properties.setProperty("GreatDeluge.Neighbours", ExamRandomMove.class.getName() + ";" + ExamRoomMove.class.getName() + ";" + ExamTimeMove.class.getName());
    105        iGD = new GreatDeluge<Exam, ExamPlacement>(properties);
    106        iUseGD = properties.getPropertyBoolean("Exam.GreatDeluge", iUseGD);
    107    }
    108
    109    /**
    110     * Initialization
    111     */
    112    @Override
    113    public void init(Solver<Exam, ExamPlacement> solver) {
    114        super.init(solver);
    115        if (iColor != null)
    116            iColor.init(solver);
    117        iCon.init(solver);
    118        iStd.init(solver);
    119        iSA.init(solver);
    120        iHC.init(solver);
    121        iFin.init(solver);
    122        iGD.init(solver);
    123        if (iTerm == null) {
    124            iTerm = solver.getTerminationCondition();
    125            solver.setTerminalCondition(this);
    126        }
    127        iFinalPhase = false;
    128        iProgress = Progress.getInstance(solver.currentSolution().getModel());
    129    }
    130
    131    /**
    132     * Neighbour selection. It consists of the following three phases:
    133     * <ul>
    134     * <li>Construction phase ({@link ExamConstruction} until all exams are
    135     * assigned)
    136     * <li>Hill-climbing phase ({@link HillClimber} until the given number
    137     * if idle iterations)
    138     * <li>Simulated annealing phase ({@link SimulatedAnnealing} until
    139     * timeout is reached)
    140     * </ul>
    141     */
    142    @SuppressWarnings("fallthrough")
    143    @Override
    144    public Neighbour<Exam, ExamPlacement> selectNeighbour(Solution<Exam, ExamPlacement> solution) {
    145        Neighbour<Exam, ExamPlacement> n = null;
    146        if (!isFinalPhase() && !iTerm.canContinue(solution))
    147            setFinalPhase(null);
    148        Context phase = getContext(solution.getAssignment());
    149        if (isFinalPhase())
    150            phase.setPhase(9999);
    151        switch (phase.getPhase()) {
    152            case -1:
    153                phase.setPhase(0);
    154                sLog.info("***** construction phase *****");
    155                if (iColor != null) {
    156                    n = iColor.selectNeighbour(solution);
    157                    if (n != null) return n;
    158                }
    159            case 0:
    160                n = iCon.selectNeighbour(solution);
    161                if (n != null)
    162                    return n;
    163                if (solution.getAssignment().nrAssignedVariables() > 0)
    164                    iProgress.setPhase("Searching for initial solution...", solution.getModel().variables().size());
    165                phase.setPhase(1);
    166                sLog.info("***** cbs/tabu-search phase *****");
    167            case 1:
    168                if (iStd != null && solution.getModel().variables().size() > solution.getAssignment().nrAssignedVariables()) {
    169                    iProgress.setProgress(solution.getModel().variables().size() - solution.getModel().getBestUnassignedVariables());
    170                    n = iStd.selectNeighbour(solution);
    171                    if (n != null)
    172                        return n;
    173                }
    174                phase.setPhase(2);
    175                sLog.info("***** hill climbing phase *****");
    176            case 2:
    177                n = iHC.selectNeighbour(solution);
    178                if (n != null)
    179                    return n;
    180                phase.setPhase(3);
    181                sLog.info("***** " + (iUseGD ? "great deluge" : "simulated annealing") + " phase *****");
    182            case 3:
    183                if (iUseGD)
    184                    return iGD.selectNeighbour(solution);
    185                else
    186                    return iSA.selectNeighbour(solution);
    187            case 9999:
    188                n = iFin.selectNeighbour(solution);
    189                if (n != null)
    190                    return n;
    191                phase.setPhase(-1);
    192                if (iFinalPhaseFinished != null && iTerm.canContinue(solution))
    193                    iFinalPhaseFinished.execute();
    194                phase.setCanContinue(false);
    195            default:
    196                return null;
    197        }
    198    }
    199
    200    /**
    201     * Set final phase
    202     *
    203     * @param finalPhaseFinished
    204     *            to be called when the final phase is finished
    205     **/
    206    public void setFinalPhase(Callback finalPhaseFinished) {
    207        sLog.info("***** final phase *****");
    208        iFinalPhaseFinished = finalPhaseFinished;
    209        iFinalPhase = true;
    210    }
    211
    212    /** Is final phase
    213     * @return true if the final phase is upon us
    214     **/
    215    public boolean isFinalPhase() {
    216        return iFinalPhase;
    217    }
    218
    219    /** Termination condition (i.e., has final phase finished) */
    220    @Override
    221    public boolean canContinue(Solution<Exam, ExamPlacement> currentSolution) {
    222        return getContext(currentSolution.getAssignment()).isCanContinue();
    223    }
    224
    225    @Override
    226    public Context createAssignmentContext(Assignment<Exam, ExamPlacement> assignment) {
    227        return new Context();
    228    }
    229
    230    public class Context implements AssignmentContext {
    231        private int iPhase = -1;
    232        private boolean iCanContinue = true;
    233
    234        public int getPhase() { return iPhase; }
    235        public void setPhase(int phase) { iPhase = phase; }
    236
    237        public boolean isCanContinue() { return iCanContinue; }
    238        public void setCanContinue(boolean canContinue) { iCanContinue = canContinue; }
    239    }
    240}