    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}