001package org.cpsolver.exam.heuristics; 002 003import org.apache.logging.log4j.Logger; 004import org.cpsolver.exam.model.Exam; 005import org.cpsolver.exam.model.ExamPlacement; 006import org.cpsolver.exam.neighbours.ExamPeriodSwapMove; 007import org.cpsolver.exam.neighbours.ExamRandomMove; 008import org.cpsolver.exam.neighbours.ExamRoomMove; 009import org.cpsolver.exam.neighbours.ExamTimeMove; 010import org.cpsolver.ifs.algorithms.GreatDeluge; 011import org.cpsolver.ifs.algorithms.HillClimber; 012import org.cpsolver.ifs.algorithms.SimulatedAnnealing; 013import org.cpsolver.ifs.assignment.Assignment; 014import org.cpsolver.ifs.assignment.context.AssignmentContext; 015import org.cpsolver.ifs.assignment.context.NeighbourSelectionWithContext; 016import org.cpsolver.ifs.heuristics.StandardNeighbourSelection; 017import org.cpsolver.ifs.model.Neighbour; 018import org.cpsolver.ifs.solution.Solution; 019import org.cpsolver.ifs.solver.Solver; 020import org.cpsolver.ifs.termination.TerminationCondition; 021import org.cpsolver.ifs.util.Callback; 022import org.cpsolver.ifs.util.DataProperties; 023import org.cpsolver.ifs.util.Progress; 024 025 026/** 027 * Examination timetabling neighbour selection. <br> 028 * <br> 029 * It consists of the following three phases: 030 * <ul> 031 * <li>Construction phase ({@link ExamConstruction} until all exams are 032 * assigned) 033 * <li>Hill-climbing phase ({@link HillClimber} until the given number if 034 * idle iterations) 035 * <li>Simulated annealing phase ({@link SimulatedAnnealing} until timeout 036 * is reached) 037 * <ul> 038 * <li>Or great deluge phase (when Exam.GreatDeluge is true, 039 * {@link GreatDeluge} until timeout is reached) 040 * </ul> 041 * <li>At the end (when {@link TerminationCondition#canContinue(Solution)} is 042 * false), the search is finished with one sweep of final phase ( 043 * {@link HillClimber} until the given number if idle iterations). 044 * </ul> 045 * <br> 046 * <br> 047 * 048 * @version ExamTT 1.3 (Examination Timetabling)<br> 049 * Copyright (C) 2008 - 2014 Tomáš Müller<br> 050 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 051 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 052 * <br> 053 * This library is free software; you can redistribute it and/or modify 054 * it under the terms of the GNU Lesser General Public License as 055 * published by the Free Software Foundation; either version 3 of the 056 * License, or (at your option) any later version. <br> 057 * <br> 058 * This library is distributed in the hope that it will be useful, but 059 * WITHOUT ANY WARRANTY; without even the implied warranty of 060 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 061 * Lesser General Public License for more details. <br> 062 * <br> 063 * You should have received a copy of the GNU Lesser General Public 064 * License along with this library; if not see 065 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 066 */ 067public class ExamNeighbourSelection extends NeighbourSelectionWithContext<Exam, ExamPlacement, ExamNeighbourSelection.Context> implements TerminationCondition<Exam, ExamPlacement> { 068 private static Logger sLog = org.apache.logging.log4j.LogManager.getLogger(ExamNeighbourSelection.class); 069 private ExamColoringConstruction iColor = null; 070 private ExamConstruction iCon = null; 071 private StandardNeighbourSelection<Exam, ExamPlacement> iStd = null; 072 private SimulatedAnnealing<Exam, ExamPlacement> iSA = null; 073 private HillClimber<Exam, ExamPlacement> iHC = null; 074 private HillClimber<Exam, ExamPlacement> iFin = null; 075 private GreatDeluge<Exam, ExamPlacement> iGD = null; 076 private boolean iUseGD = false; 077 private Progress iProgress = null; 078 private Callback iFinalPhaseFinished = null; 079 private TerminationCondition<Exam, ExamPlacement> iTerm = null; 080 private boolean iFinalPhase = false; 081 082 /** 083 * Constructor 084 * 085 * @param properties 086 * problem properties 087 */ 088 public ExamNeighbourSelection(DataProperties properties) { 089 if (properties.getPropertyBoolean("Exam.ColoringConstruction", false)) 090 iColor = new ExamColoringConstruction(properties); 091 iCon = new ExamConstruction(properties); 092 try { 093 iStd = new StandardNeighbourSelection<Exam, ExamPlacement>(properties); 094 iStd.setVariableSelection(new ExamUnassignedVariableSelection(properties)); 095 iStd.setValueSelection(new ExamTabuSearch(properties)); 096 } catch (Exception e) { 097 sLog.error("Unable to initialize standard selection, reason: " + e.getMessage(), e); 098 iStd = null; 099 } 100 properties.setProperty("SimulatedAnnealing.Neighbours", ExamRandomMove.class.getName() + ";" + ExamRoomMove.class.getName() + ";" + ExamTimeMove.class.getName() + ";" + ExamPeriodSwapMove.class.getName()); 101 iSA = new SimulatedAnnealing<Exam, ExamPlacement>(properties); 102 properties.setProperty("HillClimber.Neighbours", ExamRandomMove.class.getName() + ";" + ExamRoomMove.class.getName() + ";" + ExamTimeMove.class.getName() + ";" + ExamPeriodSwapMove.class.getName()); 103 iHC = new HillClimber<Exam, ExamPlacement>(properties); 104 iFin = new HillClimber<Exam, ExamPlacement>(properties); iFin.setPhase("Finalization"); 105 properties.setProperty("GreatDeluge.Neighbours", ExamRandomMove.class.getName() + ";" + ExamRoomMove.class.getName() + ";" + ExamTimeMove.class.getName() + ";" + ExamPeriodSwapMove.class.getName()); 106 iGD = new GreatDeluge<Exam, ExamPlacement>(properties); 107 iUseGD = properties.getPropertyBoolean("Exam.GreatDeluge", iUseGD); 108 } 109 110 /** 111 * Initialization 112 */ 113 @Override 114 public void init(Solver<Exam, ExamPlacement> solver) { 115 super.init(solver); 116 if (iColor != null) 117 iColor.init(solver); 118 iCon.init(solver); 119 iStd.init(solver); 120 iSA.init(solver); 121 iHC.init(solver); 122 iFin.init(solver); 123 iGD.init(solver); 124 if (iTerm == null) { 125 iTerm = solver.getTerminationCondition(); 126 solver.setTerminalCondition(this); 127 } 128 iFinalPhase = false; 129 iProgress = Progress.getInstance(solver.currentSolution().getModel()); 130 } 131 132 /** 133 * Neighbour selection. It consists of the following three phases: 134 * <ul> 135 * <li>Construction phase ({@link ExamConstruction} until all exams are 136 * assigned) 137 * <li>Hill-climbing phase ({@link HillClimber} until the given number 138 * if idle iterations) 139 * <li>Simulated annealing phase ({@link SimulatedAnnealing} until 140 * timeout is reached) 141 * </ul> 142 */ 143 @SuppressWarnings("fallthrough") 144 @Override 145 public Neighbour<Exam, ExamPlacement> selectNeighbour(Solution<Exam, ExamPlacement> solution) { 146 Neighbour<Exam, ExamPlacement> n = null; 147 if (!isFinalPhase() && !iTerm.canContinue(solution)) 148 setFinalPhase(null); 149 Context phase = getContext(solution.getAssignment()); 150 if (isFinalPhase()) 151 phase.setPhase(9999); 152 switch (phase.getPhase()) { 153 case -1: 154 phase.setPhase(0); 155 sLog.info("***** construction phase *****"); 156 if (iColor != null) { 157 n = iColor.selectNeighbour(solution); 158 if (n != null) return n; 159 } 160 case 0: 161 n = iCon.selectNeighbour(solution); 162 if (n != null) 163 return n; 164 if (solution.getAssignment().nrAssignedVariables() > 0) 165 iProgress.setPhase("Searching for initial solution...", solution.getModel().variables().size()); 166 phase.setPhase(1); 167 sLog.info("***** cbs/tabu-search phase *****"); 168 case 1: 169 if (iStd != null && solution.getModel().variables().size() > solution.getAssignment().nrAssignedVariables()) { 170 iProgress.setProgress(solution.getModel().variables().size() - solution.getModel().getBestUnassignedVariables()); 171 n = iStd.selectNeighbour(solution); 172 if (n != null) 173 return n; 174 } 175 phase.setPhase(2); 176 sLog.info("***** hill climbing phase *****"); 177 case 2: 178 n = iHC.selectNeighbour(solution); 179 if (n != null) 180 return n; 181 phase.setPhase(3); 182 sLog.info("***** " + (iUseGD ? "great deluge" : "simulated annealing") + " phase *****"); 183 case 3: 184 if (iUseGD) 185 return iGD.selectNeighbour(solution); 186 else 187 return iSA.selectNeighbour(solution); 188 case 9999: 189 n = iFin.selectNeighbour(solution); 190 if (n != null) 191 return n; 192 phase.setPhase(-1); 193 if (iFinalPhaseFinished != null && iTerm.canContinue(solution)) 194 iFinalPhaseFinished.execute(); 195 phase.setCanContinue(false); 196 default: 197 return null; 198 } 199 } 200 201 /** 202 * Set final phase 203 * 204 * @param finalPhaseFinished 205 * to be called when the final phase is finished 206 **/ 207 public void setFinalPhase(Callback finalPhaseFinished) { 208 sLog.info("***** final phase *****"); 209 iFinalPhaseFinished = finalPhaseFinished; 210 iFinalPhase = true; 211 } 212 213 /** Is final phase 214 * @return true if the final phase is upon us 215 **/ 216 public boolean isFinalPhase() { 217 return iFinalPhase; 218 } 219 220 /** Termination condition (i.e., has final phase finished) */ 221 @Override 222 public boolean canContinue(Solution<Exam, ExamPlacement> currentSolution) { 223 return getContext(currentSolution.getAssignment()).isCanContinue(); 224 } 225 226 @Override 227 public Context createAssignmentContext(Assignment<Exam, ExamPlacement> assignment) { 228 return new Context(); 229 } 230 231 public class Context implements AssignmentContext { 232 private int iPhase = -1; 233 private boolean iCanContinue = true; 234 235 public int getPhase() { return iPhase; } 236 public void setPhase(int phase) { iPhase = phase; } 237 238 public boolean isCanContinue() { return iCanContinue; } 239 public void setCanContinue(boolean canContinue) { iCanContinue = canContinue; } 240 } 241}