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'><caption>Related Solver Parameters</caption>
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 * @author  Tomáš Müller
058 * @version IFS 1.3 (Iterative Forward Search)<br>
059 *          Copyright (C) 2006 - 2014 Tomáš Müller<br>
060 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
061 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
062 * <br>
063 *          This library is free software; you can redistribute it and/or modify
064 *          it under the terms of the GNU Lesser General Public License as
065 *          published by the Free Software Foundation; either version 3 of the
066 *          License, or (at your option) any later version. <br>
067 * <br>
068 *          This library is distributed in the hope that it will be useful, but
069 *          WITHOUT ANY WARRANTY; without even the implied warranty of
070 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
071 *          Lesser General Public License for more details. <br>
072 * <br>
073 *          You should have received a copy of the GNU Lesser General Public
074 *          License along with this library; if not see <a href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>.
075 *
076 * @param <V> Variable
077 * @param <T> Value
078 **/
079public class StandardNeighbourSelection<V extends Variable<V, T>, T extends Value<V, T>> implements NeighbourSelection<V, T> {
080    protected static org.apache.logging.log4j.Logger sLogger = org.apache.logging.log4j.LogManager.getLogger(StandardNeighbourSelection.class);
081
082    private ValueSelection<V, T> iValueSelection = null;
083    private VariableSelection<V, T> iVariableSelection = null;
084    protected Solver<V, T> iSolver = null;
085    protected ConflictStatistics<V, T> iStat = null;
086
087    /** Sets value selection criterion 
088     * @param valueSelection value selection criterion
089     **/
090    public void setValueSelection(ValueSelection<V, T> valueSelection) {
091        iValueSelection = valueSelection;
092    }
093
094    /** Sets variable selection criterion 
095     * @param variableSelection variable selection criterion
096     **/
097    public void setVariableSelection(VariableSelection<V, T> variableSelection) {
098        iVariableSelection = variableSelection;
099    }
100
101    /** Returns value selection criterion 
102     * @return value selection criterion
103     **/
104    public ValueSelection<V, T> getValueSelection() {
105        return iValueSelection;
106    }
107
108    /** Returns variable selection criterion
109     * @return variable selection criterion
110     **/
111    public VariableSelection<V, T> getVariableSelection() {
112        return iVariableSelection;
113    }
114
115    /**
116     * Constructor
117     * 
118     * @param properties
119     *            configuration
120     * @throws Exception thrown when initialization fails
121     */
122    @SuppressWarnings("unchecked")
123    public StandardNeighbourSelection(DataProperties properties) throws Exception {
124        String valueSelectionClassName = properties.getProperty("Value.Class", "org.cpsolver.ifs.heuristics.GeneralValueSelection");
125        sLogger.info("Using " + valueSelectionClassName);
126        Class<?> valueSelectionClass = Class.forName(valueSelectionClassName);
127        Constructor<?> valueSelectionConstructor = valueSelectionClass.getConstructor(new Class[] { DataProperties.class });
128        setValueSelection((ValueSelection<V, T>) valueSelectionConstructor.newInstance(new Object[] { properties }));
129
130        String variableSelectionClassName = properties.getProperty("Variable.Class", "org.cpsolver.ifs.heuristics.GeneralVariableSelection");
131        sLogger.info("Using " + variableSelectionClassName);
132        Class<?> variableSelectionClass = Class.forName(variableSelectionClassName);
133        Constructor<?> variableSelectionConstructor = variableSelectionClass.getConstructor(new Class[] { DataProperties.class });
134        setVariableSelection((VariableSelection<V, T>) variableSelectionConstructor.newInstance(new Object[] { properties }));
135    }
136
137    /**
138     * Initialization -- methods
139     * {@link org.cpsolver.ifs.heuristics.VariableSelection#init(Solver)} and
140     * {@link org.cpsolver.ifs.heuristics.ValueSelection#init(Solver)} are
141     * called.
142     */
143    @Override
144    public void init(Solver<V, T> solver) {
145        getValueSelection().init(solver);
146        getVariableSelection().init(solver);
147        iSolver = solver;
148        for (Extension<V, T> ext: solver.getExtensions())
149            if (ext instanceof ConflictStatistics)
150                iStat = (ConflictStatistics<V, T>)ext;
151    }
152
153    /** Use the provided variable selection criterion to select a variable 
154     * @param solution current solution
155     * @return selected variable
156     **/
157    public V selectVariable(Solution<V, T> solution) {
158        // Variable selection
159        V variable = getVariableSelection().selectVariable(solution);
160        for (SolverListener<V, T> listener : iSolver.getSolverListeners())
161            if (!listener.variableSelected(solution.getAssignment(), solution.getIteration(), variable))
162                return null;
163        if (variable == null)
164            sLogger.debug("No variable selected.");
165
166        if (variable != null && variable.values(solution.getAssignment()).isEmpty()) {
167            sLogger.debug("Variable " + variable.getName() + " has no values.");
168            return null;
169        }
170        return variable;
171    }
172
173    /**
174     * Use the provided value selection criterion to select a value to the
175     * selected variable
176     * @param solution current solution
177     * @param variable selected variable
178     * @return selected value
179     */
180    @SuppressWarnings("unchecked")
181    public T selectValue(Solution<V, T> solution, V variable) {
182        // Value selection
183        T value = getValueSelection().selectValue(solution, variable);
184        for (SolverListener<V, T> listener : iSolver.getSolverListeners())
185            if (!listener.valueSelected(solution.getAssignment(), solution.getIteration(), variable, value))
186                return null;
187
188        if (value == null) {
189            sLogger.debug("No value selected for variable " + variable + ".");
190            for (Constraint<V, T> constraint: variable.hardConstraints()) {
191                if (constraint.isHard() && constraint instanceof WeakeningConstraint)
192                    ((WeakeningConstraint<V, T>)constraint).weaken(solution.getAssignment());
193            }
194            for (Constraint<V, T> constraint: solution.getModel().globalConstraints()) {
195                if (constraint.isHard() && constraint instanceof WeakeningConstraint)
196                    ((WeakeningConstraint<V, T>)constraint).weaken(solution.getAssignment());
197            }
198            return null;
199        } else {
200            for (Constraint<V, T> constraint: variable.hardConstraints()) {
201                if (constraint instanceof WeakeningConstraint && constraint.inConflict(solution.getAssignment(), value))
202                    ((WeakeningConstraint<V, T>)constraint).weaken(solution.getAssignment());
203            }
204            for (Constraint<V, T> constraint: solution.getModel().globalConstraints()) {
205                if (constraint instanceof WeakeningConstraint && constraint.inConflict(solution.getAssignment(), value))
206                    ((WeakeningConstraint<V, T>)constraint).weaken(solution.getAssignment());
207            }
208        }
209        return value;
210    }
211
212    /**
213     * Select neighbour. A value is selected to the selected variable.
214     */
215    @Override
216    public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) {
217        V variable = selectVariable(solution);
218        if (variable == null)
219            return null;
220        T value = selectValue(solution, variable);
221        if (value == null)
222            return null;
223        if (iSolver.hasSingleSolution()) {
224            Set<T> conflicts = solution.getModel().conflictValues(solution.getAssignment(), value);
225            if (iStat != null)
226                for (Map.Entry<Constraint<V, T>, Set<T>> entry: solution.getModel().conflictConstraints(solution.getAssignment(), value).entrySet())
227                    iStat.constraintAfterAssigned(solution.getAssignment(), solution.getIteration(), entry.getKey(), value, entry.getValue());
228                // for (T conflict: conflicts)
229                //      iStat.variableUnassigned(solution.getIteration(), conflict, value);
230            return new SimpleNeighbour<V, T>(variable, value, conflicts);
231        } else {
232            return new SimpleNeighbour<V, T>(variable, value);
233        }
234    }
235}