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 }