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