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}