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 private boolean iAllowUnassignments = false; 066 067 private int iTimeOut; 068 private double iStartTime; 069 070 /** 071 * Constructor 072 * @param properties problem configuration 073 * @throws Exception thrown when initialization fails (e.g., a given class is not found) 074 */ 075 public SimpleSearch(DataProperties properties) throws Exception { 076 String construction = properties.getProperty("Construction.Class"); 077 if (construction != null) { 078 try { 079 @SuppressWarnings("unchecked") 080 Class<NeighbourSelection<V, T>> constructionClass = (Class<NeighbourSelection<V, T>>)Class.forName(properties.getProperty("Construction.Class")); 081 iCon = constructionClass.getConstructor(DataProperties.class).newInstance(properties); 082 iConstructionUntilComplete = properties.getPropertyBoolean("Construction.UntilComplete", iConstructionUntilComplete); 083 } catch (Exception e) { 084 iLog.error("Unable to use " + construction + ": " + e.getMessage()); 085 } 086 } 087 iStd = new StandardNeighbourSelection<V, T>(properties); 088 iSA = new SimulatedAnnealing<V, T>(properties); 089 if (properties.getPropertyBoolean("Search.CountSteps", false)) 090 iHC = new StepCountingHillClimber<V, T>(properties); 091 else 092 iHC = new HillClimber<V, T>(properties); 093 iGD = new GreatDeluge<V, T>(properties); 094 iUseGD = properties.getPropertyBoolean("Search.GreatDeluge", iUseGD); 095 iMaxIdleIterations = properties.getPropertyInt("Search.MaxIdleIterations", iMaxIdleIterations); 096 if (iMaxIdleIterations >= 0) { 097 iStd = new MaxIdleNeighbourSelection<V, T>(properties, iStd, iMaxIdleIterations); 098 if (iCon != null && !iConstructionUntilComplete) 099 iCon = new MaxIdleNeighbourSelection<V, T>(properties, iCon, iMaxIdleIterations); 100 } 101 iTimeOut = properties.getPropertyInt("Termination.TimeOut", 1800); 102 iAllowUnassignments = properties.getPropertyBoolean("Suggestion.AllowUnassignments", iAllowUnassignments); 103 } 104 105 /** 106 * Initialization 107 */ 108 @Override 109 public void init(Solver<V, T> solver) { 110 super.init(solver); 111 if (!solver.hasSingleSolution()) 112 iCon = new ParallelConstruction<V, T>(solver.getProperties(), iCon == null ? iStd : iCon); 113 iStd.init(solver); 114 if (iCon != null) 115 iCon.init(solver); 116 iSA.init(solver); 117 iHC.init(solver); 118 iGD.init(solver); 119 iProgress = Progress.getInstance(solver.currentSolution().getModel()); 120 solver.setUpdateProgress(false); 121 iStartTime = JProf.currentTimeSec(); 122 } 123 124 protected void updateProgress(int phase, Solution<V, T> solution) { 125 if (!iHC.isMaster(solution)) return; 126 if (phase < 2) { 127 if (!"Searching for initial solution ...".equals(iProgress.getPhase())) 128 iProgress.setPhase("Searching for initial solution ...", solution.getModel().variables().size()); 129 if (solution.getModel().getBestUnassignedVariables() >= 0) 130 iProgress.setProgress(solution.getModel().variables().size() - solution.getModel().getBestUnassignedVariables()); 131 else 132 iProgress.setProgress(solution.getAssignment().nrAssignedVariables()); 133 } else { 134 if (!"Improving found solution ...".equals(iProgress.getPhase())) 135 iProgress.setPhase("Improving found solution ...", 1000l); 136 double time = JProf.currentTimeSec() - iStartTime; 137 iProgress.setProgress(Math.min(1000l, Math.round(1000 * time / iTimeOut))); 138 } 139 } 140 141 /** 142 * Neighbour selection. It consists of the following three phases: 143 * <ul> 144 * <li>Construction phase ({@link StandardNeighbourSelection} until all variables are assigned) 145 * <li>Hill-climbing phase ({@link HillClimber} until the given number if idle iterations) 146 * <li>Simulated annealing phase ({@link SimulatedAnnealing} until timeout is reached) 147 * </ul> 148 */ 149 @SuppressWarnings("fallthrough") 150 @Override 151 public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) { 152 SimpleSearchContext context = getContext(solution.getAssignment()); 153 updateProgress(context.getPhase(), solution); 154 Neighbour<V, T> n = null; 155 switch (context.getPhase()) { 156 case -1: 157 context.setPhase(0); 158 iProgress.info("[" + Thread.currentThread().getName() + "] Construction..."); 159 case 0: 160 if (iCon != null && solution.getModel().nrUnassignedVariables(solution.getAssignment()) > 0) { 161 n = iCon.selectNeighbour(solution); 162 if (n != null || iConstructionUntilComplete) 163 return n; 164 } 165 context.setPhase(1); 166 iProgress.info("[" + Thread.currentThread().getName() + "] IFS..."); 167 case 1: 168 if (iStd != null && solution.getModel().nrUnassignedVariables(solution.getAssignment()) > 0) { 169 n = iStd.selectNeighbour(solution); 170 if (n != null) return n; 171 } 172 context.setPhase(2); 173 if (solution.getModel().getBestUnassignedVariables() >= 0 && solution.getModel().getBestUnassignedVariables() < solution.getAssignment().nrUnassignedVariables(solution.getModel())) 174 solution.restoreBest(); 175 case 2: 176 if (iMaxIdleIterations < 0 && solution.getModel().nrUnassignedVariables(solution.getAssignment()) > 0) { 177 n = (iCon == null ? iStd : iCon).selectNeighbour(solution); 178 if (n != null) return n; 179 } 180 if (iMaxIdleIterations >= 0 && !iAllowUnassignments && solution.getModel().getBestUnassignedVariables() >= 0 && solution.getModel().getBestUnassignedVariables() < solution.getAssignment().nrUnassignedVariables(solution.getModel())) 181 solution.restoreBest(); 182 n = iHC.selectNeighbour(solution); 183 if (n != null) 184 return n; 185 context.setPhase(3); 186 case 3: 187 if (iMaxIdleIterations < 0 && solution.getModel().nrUnassignedVariables(solution.getAssignment()) > 0) { 188 n = (iCon == null ? iStd : iCon).selectNeighbour(solution); 189 if (n != null) return n; 190 } 191 if (iMaxIdleIterations >= 0 && !iAllowUnassignments && solution.getModel().getBestUnassignedVariables() >= 0 && solution.getModel().getBestUnassignedVariables() < solution.getAssignment().nrUnassignedVariables(solution.getModel())) 192 solution.restoreBest(); 193 if (iUseGD) 194 return iGD.selectNeighbour(solution); 195 else 196 return iSA.selectNeighbour(solution); 197 default: 198 return null; 199 } 200 } 201 202 @Override 203 public SimpleSearchContext createAssignmentContext(Assignment<V, T> assignment) { 204 return new SimpleSearchContext(); 205 } 206 207 public class SimpleSearchContext implements AssignmentContext { 208 private int iPhase = -1; 209 210 public int getPhase() { return iPhase; } 211 public void setPhase(int phase) { iPhase = phase; } 212 } 213}