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