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}