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}