001package org.cpsolver.ifs.algorithms; 002 003import org.apache.logging.log4j.Logger; 004import org.cpsolver.ifs.assignment.Assignment; 005import org.cpsolver.ifs.assignment.context.AssignmentContext; 006import org.cpsolver.ifs.assignment.context.NeighbourSelectionWithContext; 007import org.cpsolver.ifs.heuristics.MaxIdleNeighbourSelection; 008import org.cpsolver.ifs.heuristics.NeighbourSelection; 009import org.cpsolver.ifs.heuristics.StandardNeighbourSelection; 010import org.cpsolver.ifs.model.Neighbour; 011import org.cpsolver.ifs.model.Value; 012import org.cpsolver.ifs.model.Variable; 013import org.cpsolver.ifs.solution.Solution; 014import org.cpsolver.ifs.solver.Solver; 015import org.cpsolver.ifs.util.DataProperties; 016import org.cpsolver.ifs.util.JProf; 017import org.cpsolver.ifs.util.Progress; 018 019 020/** 021 * Simple search neighbour selection. <br> 022 * <br> 023 * It consists of the following three phases: 024 * <ul> 025 * <li>Construction phase ({@link StandardNeighbourSelection} until all variables are assigned) 026 * <li>Hill-climbing phase ({@link HillClimber} until the given number if idle iterations) 027 * <li>Simulated annealing phase ({@link SimulatedAnnealing} until timeout is reached) 028 * <li>Or great deluge phase (when Search.GreatDeluge is true, {@link GreatDeluge} until timeout is reached) 029 * </ul> 030 * <br> 031 * <br> 032 * 033 * @version IFS 1.3 (Iterative Forward Search)<br> 034 * Copyright (C) 2014 Tomáš Müller<br> 035 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 036 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 037 * <br> 038 * This library is free software; you can redistribute it and/or modify 039 * it under the terms of the GNU Lesser General Public License as 040 * published by the Free Software Foundation; either version 3 of the 041 * License, or (at your option) any later version. <br> 042 * <br> 043 * This library is distributed in the hope that it will be useful, but 044 * WITHOUT ANY WARRANTY; without even the implied warranty of 045 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 046 * Lesser General Public License for more details. <br> 047 * <br> 048 * You should have received a copy of the GNU Lesser General Public 049 * License along with this library; if not see 050 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 051 * @param <V> Variable 052 * @param <T> Value 053 */ 054public class SimpleSearch<V extends Variable<V, T>, T extends Value<V, T>> extends NeighbourSelectionWithContext<V,T,SimpleSearch<V,T>.SimpleSearchContext> { 055 private Logger iLog = org.apache.logging.log4j.LogManager.getLogger(SimpleSearch.class); 056 private NeighbourSelection<V, T> iCon = null; 057 private boolean iConstructionUntilComplete = false; 058 private NeighbourSelection<V, T> iStd = null; 059 private SimulatedAnnealing<V, T> iSA = null; 060 private HillClimber<V, T> iHC = null; 061 private GreatDeluge<V, T> iGD = null; 062 private boolean iUseGD = true; 063 private Progress iProgress = null; 064 private int iMaxIdleIterations = 1000; 065 066 private int iTimeOut; 067 private double iStartTime; 068 069 /** 070 * Constructor 071 * @param properties problem configuration 072 * @throws Exception thrown when initialization fails (e.g., a given class is not found) 073 */ 074 public SimpleSearch(DataProperties properties) throws Exception { 075 String construction = properties.getProperty("Construction.Class"); 076 if (construction != null) { 077 try { 078 @SuppressWarnings("unchecked") 079 Class<NeighbourSelection<V, T>> constructionClass = (Class<NeighbourSelection<V, T>>)Class.forName(properties.getProperty("Construction.Class")); 080 iCon = constructionClass.getConstructor(DataProperties.class).newInstance(properties); 081 iConstructionUntilComplete = properties.getPropertyBoolean("Construction.UntilComplete", iConstructionUntilComplete); 082 } catch (Exception e) { 083 iLog.error("Unable to use " + construction + ": " + e.getMessage()); 084 } 085 } 086 iStd = new StandardNeighbourSelection<V, T>(properties); 087 iSA = new SimulatedAnnealing<V, T>(properties); 088 if (properties.getPropertyBoolean("Search.CountSteps", false)) 089 iHC = new StepCountingHillClimber<V, T>(properties); 090 else 091 iHC = new HillClimber<V, T>(properties); 092 iGD = new GreatDeluge<V, T>(properties); 093 iUseGD = properties.getPropertyBoolean("Search.GreatDeluge", iUseGD); 094 iMaxIdleIterations = properties.getPropertyInt("Search.MaxIdleIterations", iMaxIdleIterations); 095 if (iMaxIdleIterations >= 0) { 096 iStd = new MaxIdleNeighbourSelection<V, T>(properties, iStd, iMaxIdleIterations); 097 if (iCon != null && !iConstructionUntilComplete) 098 iCon = new MaxIdleNeighbourSelection<V, T>(properties, iCon, iMaxIdleIterations); 099 } 100 iTimeOut = properties.getPropertyInt("Termination.TimeOut", 1800); 101 } 102 103 /** 104 * Initialization 105 */ 106 @Override 107 public void init(Solver<V, T> solver) { 108 super.init(solver); 109 if (!solver.hasSingleSolution()) 110 iCon = new ParallelConstruction<V, T>(solver.getProperties(), iCon == null ? iStd : iCon); 111 iStd.init(solver); 112 if (iCon != null) 113 iCon.init(solver); 114 iSA.init(solver); 115 iHC.init(solver); 116 iGD.init(solver); 117 iProgress = Progress.getInstance(solver.currentSolution().getModel()); 118 solver.setUpdateProgress(false); 119 iStartTime = JProf.currentTimeSec(); 120 } 121 122 protected void updateProgress(int phase, Solution<V, T> solution) { 123 if (!iHC.isMaster(solution)) return; 124 if (phase < 2) { 125 if (!"Searching for initial solution ...".equals(iProgress.getPhase())) 126 iProgress.setPhase("Searching for initial solution ...", solution.getModel().variables().size()); 127 if (solution.getModel().getBestUnassignedVariables() >= 0) 128 iProgress.setProgress(solution.getModel().variables().size() - solution.getModel().getBestUnassignedVariables()); 129 else 130 iProgress.setProgress(solution.getAssignment().nrAssignedVariables()); 131 } else { 132 if (!"Improving found solution ...".equals(iProgress.getPhase())) 133 iProgress.setPhase("Improving found solution ...", 1000l); 134 double time = JProf.currentTimeSec() - iStartTime; 135 iProgress.setProgress(Math.min(1000l, Math.round(1000 * time / iTimeOut))); 136 } 137 } 138 139 /** 140 * Neighbour selection. It consists of the following three phases: 141 * <ul> 142 * <li>Construction phase ({@link StandardNeighbourSelection} until all variables are assigned) 143 * <li>Hill-climbing phase ({@link HillClimber} until the given number if idle iterations) 144 * <li>Simulated annealing phase ({@link SimulatedAnnealing} until timeout is reached) 145 * </ul> 146 */ 147 @SuppressWarnings("fallthrough") 148 @Override 149 public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) { 150 SimpleSearchContext context = getContext(solution.getAssignment()); 151 updateProgress(context.getPhase(), solution); 152 Neighbour<V, T> n = null; 153 switch (context.getPhase()) { 154 case -1: 155 context.setPhase(0); 156 iProgress.info("[" + Thread.currentThread().getName() + "] Construction..."); 157 case 0: 158 if (iCon != null && solution.getModel().nrUnassignedVariables(solution.getAssignment()) > 0) { 159 n = iCon.selectNeighbour(solution); 160 if (n != null || iConstructionUntilComplete) 161 return n; 162 } 163 context.setPhase(1); 164 iProgress.info("[" + Thread.currentThread().getName() + "] IFS..."); 165 case 1: 166 if (iStd != null && solution.getModel().nrUnassignedVariables(solution.getAssignment()) > 0) { 167 n = iStd.selectNeighbour(solution); 168 if (n != null) return n; 169 } 170 context.setPhase(2); 171 if (solution.getModel().getBestUnassignedVariables() >= 0 && solution.getModel().getBestUnassignedVariables() < solution.getAssignment().nrUnassignedVariables(solution.getModel())) 172 solution.restoreBest(); 173 case 2: 174 if (iMaxIdleIterations < 0 && solution.getModel().nrUnassignedVariables(solution.getAssignment()) > 0) { 175 n = (iCon == null ? iStd : iCon).selectNeighbour(solution); 176 if (n != null) return n; 177 } 178 n = iHC.selectNeighbour(solution); 179 if (n != null) 180 return n; 181 context.setPhase(3); 182 case 3: 183 if (iMaxIdleIterations < 0 && solution.getModel().nrUnassignedVariables(solution.getAssignment()) > 0) { 184 n = (iCon == null ? iStd : iCon).selectNeighbour(solution); 185 if (n != null) return n; 186 } 187 if (iUseGD) 188 return iGD.selectNeighbour(solution); 189 else 190 return iSA.selectNeighbour(solution); 191 default: 192 return null; 193 } 194 } 195 196 @Override 197 public SimpleSearchContext createAssignmentContext(Assignment<V, T> assignment) { 198 return new SimpleSearchContext(); 199 } 200 201 public class SimpleSearchContext implements AssignmentContext { 202 private int iPhase = -1; 203 204 public int getPhase() { return iPhase; } 205 public void setPhase(int phase) { iPhase = phase; } 206 } 207}