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}