    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}