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