    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}