    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}