001package org.cpsolver.ifs.heuristics;
002
003import java.lang.reflect.Constructor;
004import java.util.Map;
005import java.util.Set;
006
007import org.cpsolver.ifs.extension.ConflictStatistics;
008import org.cpsolver.ifs.extension.Extension;
009import org.cpsolver.ifs.model.Constraint;
010import org.cpsolver.ifs.model.Neighbour;
011import org.cpsolver.ifs.model.SimpleNeighbour;
012import org.cpsolver.ifs.model.Value;
013import org.cpsolver.ifs.model.Variable;
014import org.cpsolver.ifs.model.WeakeningConstraint;
015import org.cpsolver.ifs.solution.Solution;
016import org.cpsolver.ifs.solver.Solver;
017import org.cpsolver.ifs.solver.SolverListener;
018import org.cpsolver.ifs.util.DataProperties;
019
020
021/**
022 * Standard neighbour selection criterion. <br>
023 * <br>
024 * This criterion is using the provided variable and value selection criteria.
025 * In each step, a variable is selected first using the
026 * {@link VariableSelection}. Then, a value is selected to the selected
027 * variable, using the {@link ValueSelection}. A {@link SimpleNeighbour}
028 * containing the selected value is returned. <br>
029 * <br>
030 * Note: the use of neighbour select criteria extends the former implementation
031 * of the IFS algorithm which was only able to use variable and value selection
032 * criteria and therefore only one value was assigned in each iteration. <br>
033 * <br>
034 * Parameters: <br>
035 * <table border='1' summary='Related Solver Parameters'>
036 * <tr>
037 * <th>Parameter</th>
038 * <th>Type</th>
039 * <th>Comment</th>
040 * </tr>
041 * <tr>
042 * <td>Value.Class</td>
043 * <td>{@link String}</td>
044 * <td>Fully qualified class name of the value selection criterion (see
045 * {@link ValueSelection}, e.g. {@link GeneralValueSelection})</td>
046 * </tr>
047 * <tr>
048 * <td>Variable.Class</td>
049 * <td>{@link String}</td>
050 * <td>Fully qualified class name of the variable selection criterion (see
051 * {@link VariableSelection}, e.g. {@link GeneralVariableSelection})</td>
052 * </tr>
053 * </table>
054 * 
055 * @see Solver
056 * 
057 * @version IFS 1.3 (Iterative Forward Search)<br>
058 *          Copyright (C) 2006 - 2014 Tomáš Müller<br>
059 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
060 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
061 * <br>
062 *          This library is free software; you can redistribute it and/or modify
063 *          it under the terms of the GNU Lesser General Public License as
064 *          published by the Free Software Foundation; either version 3 of the
065 *          License, or (at your option) any later version. <br>
066 * <br>
067 *          This library is distributed in the hope that it will be useful, but
068 *          WITHOUT ANY WARRANTY; without even the implied warranty of
069 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
070 *          Lesser General Public License for more details. <br>
071 * <br>
072 *          You should have received a copy of the GNU Lesser General Public
073 *          License along with this library; if not see <a href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>.
074 *
075 * @param <V> Variable
076 * @param <T> Value
077 **/
078public class StandardNeighbourSelection<V extends Variable<V, T>, T extends Value<V, T>> implements NeighbourSelection<V, T> {
079    protected static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(StandardNeighbourSelection.class);
080
081    private ValueSelection<V, T> iValueSelection = null;
082    private VariableSelection<V, T> iVariableSelection = null;
083    private Solver<V, T> iSolver = null;
084    private ConflictStatistics<V, T> iStat = null;
085
086    /** Sets value selection criterion 
087     * @param valueSelection value selection criterion
088     **/
089    public void setValueSelection(ValueSelection<V, T> valueSelection) {
090        iValueSelection = valueSelection;
091    }
092
093    /** Sets variable selection criterion 
094     * @param variableSelection variable selection criterion
095     **/
096    public void setVariableSelection(VariableSelection<V, T> variableSelection) {
097        iVariableSelection = variableSelection;
098    }
099
100    /** Returns value selection criterion 
101     * @return value selection criterion
102     **/
103    public ValueSelection<V, T> getValueSelection() {
104        return iValueSelection;
105    }
106
107    /** Returns variable selection criterion
108     * @return variable selection criterion
109     **/
110    public VariableSelection<V, T> getVariableSelection() {
111        return iVariableSelection;
112    }
113
114    /**
115     * Constructor
116     * 
117     * @param properties
118     *            configuration
119     * @throws Exception thrown when initialization fails
120     */
121    @SuppressWarnings("unchecked")
122    public StandardNeighbourSelection(DataProperties properties) throws Exception {
123        String valueSelectionClassName = properties.getProperty("Value.Class", "org.cpsolver.ifs.heuristics.GeneralValueSelection");
124        sLogger.info("Using " + valueSelectionClassName);
125        Class<?> valueSelectionClass = Class.forName(valueSelectionClassName);
126        Constructor<?> valueSelectionConstructor = valueSelectionClass.getConstructor(new Class[] { DataProperties.class });
127        setValueSelection((ValueSelection<V, T>) valueSelectionConstructor.newInstance(new Object[] { properties }));
128
129        String variableSelectionClassName = properties.getProperty("Variable.Class", "org.cpsolver.ifs.heuristics.GeneralVariableSelection");
130        sLogger.info("Using " + variableSelectionClassName);
131        Class<?> variableSelectionClass = Class.forName(variableSelectionClassName);
132        Constructor<?> variableSelectionConstructor = variableSelectionClass.getConstructor(new Class[] { DataProperties.class });
133        setVariableSelection((VariableSelection<V, T>) variableSelectionConstructor.newInstance(new Object[] { properties }));
134    }
135
136    /**
137     * Initialization -- methods
138     * {@link org.cpsolver.ifs.heuristics.VariableSelection#init(Solver)} and
139     * {@link org.cpsolver.ifs.heuristics.ValueSelection#init(Solver)} are
140     * called.
141     */
142    @Override
143    public void init(Solver<V, T> solver) {
144        getValueSelection().init(solver);
145        getVariableSelection().init(solver);
146        iSolver = solver;
147        for (Extension<V, T> ext: solver.getExtensions())
148            if (ext instanceof ConflictStatistics)
149                iStat = (ConflictStatistics<V, T>)ext;
150    }
151
152    /** Use the provided variable selection criterion to select a variable 
153     * @param solution current solution
154     * @return selected variable
155     **/
156    public V selectVariable(Solution<V, T> solution) {
157        // Variable selection
158        V variable = getVariableSelection().selectVariable(solution);
159        for (SolverListener<V, T> listener : iSolver.getSolverListeners())
160            if (!listener.variableSelected(solution.getAssignment(), solution.getIteration(), variable))
161                return null;
162        if (variable == null)
163            sLogger.debug("No variable selected.");
164
165        if (variable != null && variable.values(solution.getAssignment()).isEmpty()) {
166            sLogger.debug("Variable " + variable.getName() + " has no values.");
167            return null;
168        }
169        return variable;
170    }
171
172    /**
173     * Use the provided value selection criterion to select a value to the
174     * selected variable
175     * @param solution current solution
176     * @param variable selected variable
177     * @return selected value
178     */
179    @SuppressWarnings("unchecked")
180    public T selectValue(Solution<V, T> solution, V variable) {
181        // Value selection
182        T value = getValueSelection().selectValue(solution, variable);
183        for (SolverListener<V, T> listener : iSolver.getSolverListeners())
184            if (!listener.valueSelected(solution.getAssignment(), solution.getIteration(), variable, value))
185                return null;
186
187        if (value == null) {
188            sLogger.debug("No value selected for variable " + variable + ".");
189            for (Constraint<V, T> constraint: variable.hardConstraints()) {
190                if (constraint.isHard() && constraint instanceof WeakeningConstraint)
191                    ((WeakeningConstraint<V, T>)constraint).weaken(solution.getAssignment());
192            }
193            for (Constraint<V, T> constraint: solution.getModel().globalConstraints()) {
194                if (constraint.isHard() && constraint instanceof WeakeningConstraint)
195                    ((WeakeningConstraint<V, T>)constraint).weaken(solution.getAssignment());
196            }
197            return null;
198        } else {
199            for (Constraint<V, T> constraint: variable.hardConstraints()) {
200                if (constraint instanceof WeakeningConstraint && constraint.inConflict(solution.getAssignment(), value))
201                    ((WeakeningConstraint<V, T>)constraint).weaken(solution.getAssignment());
202            }
203            for (Constraint<V, T> constraint: solution.getModel().globalConstraints()) {
204                if (constraint instanceof WeakeningConstraint && constraint.inConflict(solution.getAssignment(), value))
205                    ((WeakeningConstraint<V, T>)constraint).weaken(solution.getAssignment());
206            }
207        }
208        return value;
209    }
210
211    /**
212     * Select neighbour. A value is selected to the selected variable.
213     */
214    @Override
215    public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) {
216        V variable = selectVariable(solution);
217        if (variable == null)
218            return null;
219        T value = selectValue(solution, variable);
220        if (value == null)
221            return null;
222        if (iSolver.hasSingleSolution()) {
223            Set<T> conflicts = solution.getModel().conflictValues(solution.getAssignment(), value);
224            if (iStat != null)
225                for (Map.Entry<Constraint<V, T>, Set<T>> entry: solution.getModel().conflictConstraints(solution.getAssignment(), value).entrySet())
226                    iStat.constraintAfterAssigned(solution.getAssignment(), solution.getIteration(), entry.getKey(), value, entry.getValue());
227                // for (T conflict: conflicts)
228                //      iStat.variableUnassigned(solution.getIteration(), conflict, value);
229            return new SimpleNeighbour<V, T>(variable, value, conflicts);
230        } else {
231            return new SimpleNeighbour<V, T>(variable, value);
232        }
233    }
234}