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