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}