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