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