001package net.sf.cpsolver.ifs.algorithms;
002
003import org.apache.log4j.Logger;
004
005import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
006import net.sf.cpsolver.ifs.heuristics.StandardNeighbourSelection;
007import net.sf.cpsolver.ifs.model.Neighbour;
008import net.sf.cpsolver.ifs.model.Value;
009import net.sf.cpsolver.ifs.model.Variable;
010import net.sf.cpsolver.ifs.solution.Solution;
011import net.sf.cpsolver.ifs.solver.Solver;
012import net.sf.cpsolver.ifs.termination.TerminationCondition;
013import net.sf.cpsolver.ifs.util.Callback;
014import net.sf.cpsolver.ifs.util.DataProperties;
015import net.sf.cpsolver.ifs.util.Progress;
016
017/**
018 * Simple search neighbour selection. <br>
019 * <br>
020 * It consists of the following three phases:
021 * <ul>
022 * <li>Construction phase ({@link StandardNeighbourSelection} until all variables are assigned)
023 * <li>Hill-climbing phase ({@link HillClimber} until the given number if idle iterations)
024 * <li>Simulated annealing phase ({@link SimulatedAnnealing} until timeout is reached)
025 * <ul>
026 * <li>Or great deluge phase (when Search.GreatDeluge is true, {@link GreatDeluge} until timeout is reached)
027 * </ul>
028 * <li>At the end (when {@link TerminationCondition#canContinue(Solution)} is false),
029 * the search is finished with one sweep of final phase ({@link HillClimber} until the given number if idle iterations).
030 * </ul>
031 * <br>
032 * <br>
033 * 
034 * @version IFS 1.2 (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 */
053public class SimpleSearch<V extends Variable<V, T>, T extends Value<V, T>> implements NeighbourSelection<V, T>, TerminationCondition<V, T> {
054    private Logger iLog = Logger.getLogger(SimpleSearch.class);
055    private NeighbourSelection<V, T> iCon = null;
056    private boolean iConstructionUntilComplete = false; 
057    private StandardNeighbourSelection<V, T> iStd = null;
058    private SimulatedAnnealing<V, T> iSA = null;
059    private HillClimber<V, T> iHC = null;
060    private HillClimber<V, T> iFin = null;
061    private GreatDeluge<V, T> iGD = null;
062    private int iPhase = -1;
063    private boolean iUseGD = true;
064    private Progress iProgress = null;
065    private Callback iFinalPhaseFinished = null;
066    private boolean iCanContinue = true;
067    private TerminationCondition<V, T> iTerm = null;
068
069    /**
070     * Constructor
071     * 
072     * @param properties
073     *            problem properties
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, "Step Counting Hill Climbing");
091        else
092            iHC = new HillClimber<V, T>(properties);
093        iFin = new HillClimber<V, T>(properties); iFin.setPhase("Finalization");
094        iGD = new GreatDeluge<V, T>(properties);
095        iUseGD = properties.getPropertyBoolean("Search.GreatDeluge", iUseGD);
096    }
097
098    /**
099     * Initialization
100     */
101    @Override
102    public void init(Solver<V, T> solver) {
103        iStd.init(solver);
104        if (iCon != null)
105            iCon.init(solver);
106        iSA.init(solver);
107        iHC.init(solver);
108        iFin.init(solver);
109        iGD.init(solver);
110        if (iTerm == null) {
111            iTerm = solver.getTerminationCondition();
112            solver.setTerminalCondition(this);
113        }
114        iCanContinue = true;
115        iProgress = Progress.getInstance(solver.currentSolution().getModel());
116    }
117
118    /**
119     * Neighbour selection. It consists of the following three phases:
120     * <ul>
121     * <li>Construction phase ({@link StandardNeighbourSelection} until all variables are assigned)
122     * <li>Hill-climbing phase ({@link HillClimber} until the given number if idle iterations)
123     * <li>Simulated annealing phase ({@link SimulatedAnnealing} until timeout is reached)
124     * </ul>
125     */
126    @SuppressWarnings("fallthrough")
127    @Override
128    public synchronized Neighbour<V, T> selectNeighbour(Solution<V, T> solution) {
129        Neighbour<V, T> n = null;
130        if (!isFinalPhase() && !iTerm.canContinue(solution))
131            setFinalPhase(null);
132        switch (iPhase) {
133            case -1:
134                iPhase++;
135                iLog.info("***** construction phase *****");
136                if (solution.getModel().nrUnassignedVariables() > 0)
137                    iProgress.setPhase("Searching for initial solution...", solution.getModel().variables().size());
138            case 0:
139                if (iCon != null && solution.getModel().nrUnassignedVariables() > 0) {
140                    iProgress.setProgress(solution.getModel().variables().size() - solution.getModel().getBestUnassignedVariables());
141                    n = iCon.selectNeighbour(solution);
142                    if (n != null || iConstructionUntilComplete)
143                        return n;
144                }
145                iPhase++;
146                iLog.info("***** ifs phase *****");
147            case 1:
148                if (iStd != null && solution.getModel().nrUnassignedVariables() > 0) {
149                    iProgress.setProgress(solution.getModel().variables().size() - solution.getModel().getBestUnassignedVariables());
150                    return iStd.selectNeighbour(solution);
151                }
152                iPhase++;
153                iLog.info("***** hill climbing phase *****");
154            case 2:
155                if (solution.getModel().nrUnassignedVariables() > 0)
156                    return (iCon == null ? iStd : iCon).selectNeighbour(solution);
157                n = iHC.selectNeighbour(solution);
158                if (n != null)
159                    return n;
160                iPhase++;
161                iLog.info("***** " + (iUseGD ? "great deluge" : "simulated annealing") + " phase *****");
162            case 3:
163                if (solution.getModel().nrUnassignedVariables() > 0)
164                    return (iCon == null ? iStd : iCon).selectNeighbour(solution);
165                if (iUseGD)
166                    return iGD.selectNeighbour(solution);
167                else
168                    return iSA.selectNeighbour(solution);
169            case 9999:
170                n = iFin.selectNeighbour(solution);
171                if (n != null)
172                    return n;
173                iPhase = -1;
174                if (iFinalPhaseFinished != null)
175                    iFinalPhaseFinished.execute();
176                iCanContinue = false;
177            default:
178                return null;
179        }
180    }
181
182    /**
183     * Set final phase
184     * 
185     * @param finalPhaseFinished
186     *            to be called when the final phase is finished
187     **/
188    public synchronized void setFinalPhase(Callback finalPhaseFinished) {
189        iLog.info("***** final phase *****");
190        iFinalPhaseFinished = finalPhaseFinished;
191        iPhase = 9999;
192    }
193
194    /** Is final phase */
195    public boolean isFinalPhase() {
196        return iPhase == 9999;
197    }
198
199    /** Termination condition (i.e., has final phase finished) */
200    @Override
201    public boolean canContinue(Solution<V, T> currentSolution) {
202        return iCanContinue;
203    }
204
205}