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