001package org.cpsolver.ifs.algorithms;
002
003import org.apache.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 = Logger.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}