001 package net.sf.cpsolver.exam.heuristics;
002
003 import org.apache.log4j.Logger;
004
005 import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
006 import net.sf.cpsolver.ifs.heuristics.StandardNeighbourSelection;
007 import net.sf.cpsolver.ifs.model.Neighbour;
008 import net.sf.cpsolver.ifs.solution.Solution;
009 import net.sf.cpsolver.ifs.solver.Solver;
010 import net.sf.cpsolver.ifs.termination.TerminationCondition;
011 import net.sf.cpsolver.ifs.util.Callback;
012 import net.sf.cpsolver.ifs.util.DataProperties;
013 import net.sf.cpsolver.ifs.util.Progress;
014
015 /**
016 * Examination timetabling neighbour selection.
017 * <br><br>
018 * It consists of the following three phases:
019 * <ul>
020 * <li>Construction phase ({@link ExamConstruction} until all exams are assigned)
021 * <li>Hill-climbing phase ({@link ExamHillClimbing} until the given number if idle iterations)
022 * <li>Simulated annealing phase ({@link ExamSimulatedAnnealing} until timeout is reached)
023 * <ul>
024 * <li>Or greate deluge phase (when Exam.GreatDeluge is true,{@link ExamGreatDeluge} until timeout is reached)
025 * </ul>
026 * <li>At the end (when {@link TerminationCondition#canContinue(Solution)} is false), the search is finished with one sweep
027 * of final phase ({@link ExamHillClimbing} until the given number if idle iterations).
028 * </ul>
029 * <br><br>
030 *
031 * @version
032 * ExamTT 1.1 (Examination Timetabling)<br>
033 * Copyright (C) 2008 Tomáš Müller<br>
034 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
035 * Lazenska 391, 76314 Zlin, Czech Republic<br>
036 * <br>
037 * This library is free software; you can redistribute it and/or
038 * modify it under the terms of the GNU Lesser General Public
039 * License as published by the Free Software Foundation; either
040 * version 2.1 of the License, or (at your option) any later version.
041 * <br><br>
042 * This library is distributed in the hope that it will be useful,
043 * but WITHOUT ANY WARRANTY; without even the implied warranty of
044 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
045 * Lesser General Public License for more details.
046 * <br><br>
047 * You should have received a copy of the GNU Lesser General Public
048 * License along with this library; if not, write to the Free Software
049 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
050 */
051 public class ExamNeighbourSelection implements NeighbourSelection, TerminationCondition {
052 private static Logger sLog = Logger.getLogger(ExamNeighbourSelection.class);
053 private ExamConstruction iCon = null;
054 private StandardNeighbourSelection iStd = null;
055 private ExamSimulatedAnnealing iSA = null;
056 private ExamHillClimbing iHC = null;
057 private ExamHillClimbing iFin = null;
058 private ExamGreatDeluge iGD = null;
059 private int iPhase = -1;
060 private boolean iUseGD = false;
061 private Progress iProgress = null;
062 private Callback iFinalPhaseFinished = null;
063 private boolean iCanContinue = true;
064 private TerminationCondition iTerm = null;
065
066 /**
067 * Constructor
068 * @param properties problem properties
069 */
070 public ExamNeighbourSelection(DataProperties properties) {
071 iCon = new ExamConstruction(properties);
072 try {
073 iStd = new StandardNeighbourSelection(properties);
074 iStd.setVariableSelection(new ExamUnassignedVariableSelection(properties));
075 iStd.setValueSelection(new ExamTabuSearch(properties));
076 } catch (Exception e) {
077 sLog.error("Unable to initialize standard selection, reason: "+e.getMessage(),e);
078 iStd = null;
079 }
080 iSA = new ExamSimulatedAnnealing(properties);
081 iHC = new ExamHillClimbing(properties,"Hill Climbing");
082 iFin = new ExamHillClimbing(properties,"Finalization");
083 iGD = new ExamGreatDeluge(properties);
084 iUseGD = properties.getPropertyBoolean("Exam.GreatDeluge", iUseGD);
085 }
086
087 /**
088 * Initialization
089 */
090 public void init(Solver solver){
091 iCon.init(solver);
092 iStd.init(solver);
093 iSA.init(solver);
094 iHC.init(solver);
095 iFin.init(solver);
096 iGD.init(solver);
097 if (iTerm==null) {
098 iTerm = solver.getTerminationCondition();
099 solver.setTerminalCondition(this);
100 }
101 iCanContinue = true;
102 iProgress = Progress.getInstance(solver.currentSolution().getModel());
103 }
104
105 /**
106 * Neighbour selection. It consists of the following three phases:
107 * <ul>
108 * <li>Construction phase ({@link ExamConstruction} until all exams are assigned)
109 * <li>Hill-climbing phase ({@link ExamHillClimbing} until the given number if idle iterations)
110 * <li>Simulated annealing phase ({@link ExamSimulatedAnnealing} until timeout is reached)
111 * </ul>
112 */
113 public synchronized Neighbour selectNeighbour(Solution solution) {
114 Neighbour n = null;
115 if (!isFinalPhase() && !iTerm.canContinue(solution)) setFinalPhase(null);
116 switch (iPhase) {
117 case -1 :
118 iPhase++;
119 sLog.info("***** construction phase *****");
120 case 0 :
121 n = iCon.selectNeighbour(solution);
122 if (n!=null) return n;
123 if (solution.getModel().nrUnassignedVariables()>0)
124 iProgress.setPhase("Searching for initial solution...", solution.getModel().variables().size());
125 iPhase++;
126 sLog.info("***** cbs/tabu-search phase *****");
127 case 1 :
128 if (iStd!=null && solution.getModel().nrUnassignedVariables()>0) {
129 iProgress.setProgress(solution.getModel().variables().size()-solution.getModel().getBestUnassignedVariables());
130 n = iStd.selectNeighbour(solution);
131 if (n!=null) return n;
132 }
133 iPhase++;
134 sLog.info("***** hill climbing phase *****");
135 case 2 :
136 n = iHC.selectNeighbour(solution);
137 if (n!=null) return n;
138 iPhase++;
139 sLog.info("***** "+(iUseGD?"great deluge":"simulated annealing")+" phase *****");
140 case 3 :
141 if (iUseGD)
142 return iGD.selectNeighbour(solution);
143 else
144 return iSA.selectNeighbour(solution);
145 case 9999 :
146 n = iFin.selectNeighbour(solution);
147 if (n!=null) return n;
148 iPhase = -1;
149 if (iFinalPhaseFinished!=null) iFinalPhaseFinished.execute();
150 iCanContinue = false;
151 default :
152 return null;
153 }
154 }
155
156 /** Set final phase
157 * @param finalPhaseFinished to be called when the final phase is finished
158 **/
159 public synchronized void setFinalPhase(Callback finalPhaseFinished) {
160 sLog.info("***** final phase *****");
161 iFinalPhaseFinished = finalPhaseFinished;
162 iPhase = 9999;
163 }
164
165 /** Is final phase */
166 public boolean isFinalPhase() {
167 return iPhase == 9999;
168 }
169
170 /** Termination condition (i.e., has final phase finished)*/
171 public boolean canContinue(Solution currentSolution) {
172 return iCanContinue;
173 }
174
175 }