001    package net.sf.cpsolver.exam.heuristics;
002    
003    import org.apache.log4j.Logger;
004    
005    import net.sf.cpsolver.exam.model.Exam;
006    import net.sf.cpsolver.exam.model.ExamPlacement;
007    import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
008    import net.sf.cpsolver.ifs.heuristics.StandardNeighbourSelection;
009    import net.sf.cpsolver.ifs.model.Neighbour;
010    import net.sf.cpsolver.ifs.solution.Solution;
011    import net.sf.cpsolver.ifs.solver.Solver;
012    import net.sf.cpsolver.ifs.termination.TerminationCondition;
013    import net.sf.cpsolver.ifs.util.Callback;
014    import net.sf.cpsolver.ifs.util.DataProperties;
015    import 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 Tomas Muller<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     */
058    public 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    }