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