    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.NeighbourSelection;
    008import org.cpsolver.ifs.heuristics.StandardNeighbourSelection;
    009import org.cpsolver.ifs.model.Neighbour;
    010import org.cpsolver.ifs.model.Value;
    011import org.cpsolver.ifs.model.Variable;
    012import org.cpsolver.ifs.solution.Solution;
    013import org.cpsolver.ifs.solver.Solver;
    014import org.cpsolver.ifs.util.DataProperties;
    015import org.cpsolver.ifs.util.Progress;
    016
    017
    018/**
    019 * Simple search neighbour selection. <br>
    020 * <br>
    021 * It consists of the following three phases:
    022 * <ul>
    023 * <li>Construction phase ({@link StandardNeighbourSelection} until all variables are assigned)
    024 * <li>Hill-climbing phase ({@link HillClimber} until the given number if idle iterations)
    025 * <li>Simulated annealing phase ({@link SimulatedAnnealing} until timeout is reached)
    026 * <li>Or great deluge phase (when Search.GreatDeluge is true, {@link GreatDeluge} until timeout is reached)
    027 * </ul>
    028 * <br>
    029 * <br>
    030 *
    031 * @version IFS 1.3 (Iterative Forward Search)<br>
    032 *          Copyright (C) 2014 Tomáš Müller<br>
    033 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    034 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    035 * <br>
    036 *          This library is free software; you can redistribute it and/or modify
    037 *          it under the terms of the GNU Lesser General Public License as
    038 *          published by the Free Software Foundation; either version 3 of the
    039 *          License, or (at your option) any later version. <br>
    040 * <br>
    041 *          This library is distributed in the hope that it will be useful, but
    042 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    043 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    044 *          Lesser General Public License for more details. <br>
    045 * <br>
    046 *          You should have received a copy of the GNU Lesser General Public
    047 *          License along with this library; if not see
    048 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    049 * @param <V> Variable
    050 * @param <T> Value
    051 */
    052public class SimpleSearch<V extends Variable<V, T>, T extends Value<V, T>> extends NeighbourSelectionWithContext<V,T,SimpleSearch<V,T>.SimpleSearchContext> {
    053    private Logger iLog = org.apache.logging.log4j.LogManager.getLogger(SimpleSearch.class);
    054    private NeighbourSelection<V, T> iCon = null;
    055    private boolean iConstructionUntilComplete = false;
    056    private StandardNeighbourSelection<V, T> iStd = null;
    057    private SimulatedAnnealing<V, T> iSA = null;
    058    private HillClimber<V, T> iHC = null;
    059    private GreatDeluge<V, T> iGD = null;
    060    private boolean iUseGD = true;
    061    private Progress iProgress = null;
    062
    063    /**
    064     * Constructor
    065     * @param properties problem configuration
    066     * @throws Exception thrown when initialization fails (e.g., a given class is not found)
    067     */
    068    public SimpleSearch(DataProperties properties) throws Exception {
    069        String construction = properties.getProperty("Construction.Class");
    070        if (construction != null) {
    071            try {
    072                @SuppressWarnings("unchecked")
    073                Class<NeighbourSelection<V, T>> constructionClass = (Class<NeighbourSelection<V, T>>)Class.forName(properties.getProperty("Construction.Class"));
    074                iCon = constructionClass.getConstructor(DataProperties.class).newInstance(properties);
    075                iConstructionUntilComplete = properties.getPropertyBoolean("Construction.UntilComplete", iConstructionUntilComplete);
    076            } catch (Exception e) {
    077                iLog.error("Unable to use " + construction + ": " + e.getMessage());
    078            }
    079        }
    080        iStd = new StandardNeighbourSelection<V, T>(properties);
    081        iSA = new SimulatedAnnealing<V, T>(properties);
    082        if (properties.getPropertyBoolean("Search.CountSteps", false))
    083            iHC = new StepCountingHillClimber<V, T>(properties);
    084        else
    085            iHC = new HillClimber<V, T>(properties);
    086        iGD = new GreatDeluge<V, T>(properties);
    087        iUseGD = properties.getPropertyBoolean("Search.GreatDeluge", iUseGD);
    088    }
    089
    090    /**
    091     * Initialization
    092     */
    093    @Override
    094    public void init(Solver<V, T> solver) {
    095        super.init(solver);
    096        if (!solver.hasSingleSolution())
    097            iCon = new ParallelConstruction<V, T>(solver.getProperties(), iCon == null ? iStd : iCon);
    098        iStd.init(solver);
    099        if (iCon != null)
    100            iCon.init(solver);
    101        iSA.init(solver);
    102        iHC.init(solver);
    103        iGD.init(solver);
    104        iProgress = Progress.getInstance(solver.currentSolution().getModel());
    105    }
    106
    107    /**
    108     * Neighbour selection. It consists of the following three phases:
    109     * <ul>
    110     * <li>Construction phase ({@link StandardNeighbourSelection} until all variables are assigned)
    111     * <li>Hill-climbing phase ({@link HillClimber} until the given number if idle iterations)
    112     * <li>Simulated annealing phase ({@link SimulatedAnnealing} until timeout is reached)
    113     * </ul>
    114     */
    115    @SuppressWarnings("fallthrough")
    116    @Override
    117    public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) {
    118        SimpleSearchContext context = getContext(solution.getAssignment());
    119        Neighbour<V, T> n = null;
    120        switch (context.getPhase()) {
    121            case -1:
    122                context.setPhase(0);
    123                iProgress.info("[" + Thread.currentThread().getName() + "] Construction...");
    124            case 0:
    125                if (iCon != null && solution.getModel().nrUnassignedVariables(solution.getAssignment()) > 0) {
    126                    n = iCon.selectNeighbour(solution);
    127                    if (n != null || iConstructionUntilComplete)
    128                        return n;
    129                }
    130                context.setPhase(1);
    131                iProgress.info("[" + Thread.currentThread().getName() + "] IFS...");
    132            case 1:
    133                if (iStd != null && solution.getModel().nrUnassignedVariables(solution.getAssignment()) > 0) {
    134                    return iStd.selectNeighbour(solution);
    135                }
    136                context.setPhase(2);
    137            case 2:
    138                if (solution.getModel().nrUnassignedVariables(solution.getAssignment()) > 0)
    139                    return (iCon == null ? iStd : iCon).selectNeighbour(solution);
    140                n = iHC.selectNeighbour(solution);
    141                if (n != null)
    142                    return n;
    143                context.setPhase(3);
    144            case 3:
    145                if (solution.getModel().nrUnassignedVariables(solution.getAssignment()) > 0)
    146                    return (iCon == null ? iStd : iCon).selectNeighbour(solution);
    147                if (iUseGD)
    148                    return iGD.selectNeighbour(solution);
    149                else
    150                    return iSA.selectNeighbour(solution);
    151            default:
    152                return null;
    153        }
    154    }
    155
    156    @Override
    157    public SimpleSearchContext createAssignmentContext(Assignment<V, T> assignment) {
    158        return new SimpleSearchContext();
    159    }
    160
    161    public class SimpleSearchContext implements AssignmentContext {
    162        private int iPhase = -1;
    163
    164        public int getPhase() { return iPhase; }
    165        public void setPhase(int phase) { iPhase = phase; }
    166    }
    167}