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