    001package org.cpsolver.ifs.dbt;
    002
    003import java.util.HashSet;
    004import java.util.Set;
    005
    006import org.cpsolver.ifs.assignment.Assignment;
    007import org.cpsolver.ifs.extension.MacPropagation;
    008import org.cpsolver.ifs.model.Neighbour;
    009import org.cpsolver.ifs.model.Value;
    010import org.cpsolver.ifs.model.Variable;
    011import org.cpsolver.ifs.solution.Solution;
    012import org.cpsolver.ifs.solver.Solver;
    013import org.cpsolver.ifs.solver.SolverListener;
    014import org.cpsolver.ifs.util.DataProperties;
    015
    016
    017/**
    018 * Maintenance of arc consistency in dynamic backtracking. <br>
    019 * <br>
    020 * The difference between {@link MacPropagation} and this DBT propagation is
    021 * that all not-assigned values of an assigned variable are marked as nogood.
    022 * Also, when a dead end is reached, unassignment or failure takes place. <br>
    023 * <br>
    024 * This IFS solver extension is to be used only in case of dynamic backtracking
    025 * and it has no parameters.
    026 *
    027 *
    028 * @version IFS 1.3 (Iterative Forward Search)<br>
    029 *          Copyright (C) 2006 - 2014 Tomáš Müller<br>
    030 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    031 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    032 * <br>
    033 *          This library is free software; you can redistribute it and/or modify
    034 *          it under the terms of the GNU Lesser General Public License as
    035 *          published by the Free Software Foundation; either version 3 of the
    036 *          License, or (at your option) any later version. <br>
    037 * <br>
    038 *          This library is distributed in the hope that it will be useful, but
    039 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    040 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    041 *          Lesser General Public License for more details. <br>
    042 * <br>
    043 *          You should have received a copy of the GNU Lesser General Public
    044 *          License along with this library; if not see <a href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>.
    045 * @param <V> Variable
    046 * @param <T> Value
    047 *
    048 */
    049public class DbtPropagation<V extends Variable<V, T>, T extends Value<V, T>> extends MacPropagation<V, T> implements SolverListener<V, T> {
    050    private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(DbtPropagation.class);
    051
    052    /**
    053     * Constructor. No parameter is taken from properties.
    054     * @param solver current solver
    055     * @param properties solver configuration
    056     */
    057    public DbtPropagation(Solver<V, T> solver, DataProperties properties) {
    058        super(solver, properties);
    059        solver.addSolverListener(this);
    060    }
    061
    062    /**
    063     * Propagation takes place every time a value is assigned to a variable. <br>
    064     * <br>
    065     * <ul>
    066     * <li>Prints a warning if the value is nogood (should not never happen),
    067     * <li>sets all other values of the variable to nogood (explanation is the assigned value itself),
    068     * <li>runs propagation.
    069     * </ul>
    070     *
    071     * @see MacPropagation#propagate(Assignment, Variable)
    072     */
    073    @Override
    074    public void afterAssigned(Assignment<V, T> assignment, long iteration, T value) {
    075        iIteration = iteration;
    076        if (!isGood(assignment, value)) {
    077            sLogger.warn(value.variable().getName() + " = " + value.getName() + " -- not good value assigned (noGood:" + noGood(assignment, value) + ")");
    078            setGood(assignment, value);
    079        }
    080
    081        Set<T> noGood = new HashSet<T>(1);
    082
    083        noGood.add(value);
    084        for (T anotherValue : value.variable().values(assignment)) {
    085            if (anotherValue.equals(value) || !isGood(assignment, anotherValue))
    086                continue;
    087            setNoGood(assignment, anotherValue, noGood);
    088        }
    089        propagate(assignment, value.variable());
    090    }
    091
    092    /**
    093     * Undo propagation when a value is unassigned. <br>
    094     * <br>
    095     * <ul>
    096     * <li>Prints an error if the value is nogood (should not never happen),
    097     * <li>runs propagation undo.
    098     * </ul>
    099     *
    100     * @see MacPropagation#undoPropagate(Assignment, Variable)
    101     */
    102    @Override
    103    public void afterUnassigned(Assignment<V, T> assignment, long iteration, T value) {
    104        iIteration = iteration;
    105        if (!isGood(assignment, value)) {
    106            sLogger.error(value.variable().getName() + " = " + value.getName()
    107                    + " -- not good value unassigned (noGood:" + noGood(assignment, value) + ")");
    108        }
    109        undoPropagate(assignment, value.variable());
    110    }
    111
    112    /**
    113     * If no variable is selected (all variables are assinged), unassign the
    114     * last assigned variable. <br>
    115     * <br>
    116     * Do not allow to select an assigned variable. <br>
    117     * <br>
    118     * If no variable is selected (because all variables are assigned, see
    119     * {@link DbtVariableSelection}):
    120     * <ul>
    121     * <li>find the last assigned variable and
    122     * <li>unassign it (explanation is a union of assignments of all other
    123     * variables).
    124     * </ul>
    125     *
    126     * @see DbtVariableSelection#selectVariable(Solution)
    127     */
    128    @Override
    129    public boolean variableSelected(Assignment<V, T> assignment, long iteration, V variable) {
    130        if (variable == null) {
    131            sLogger.debug("No variable selected -> backtrack.");
    132            V lastVariable = null;
    133
    134            for (V var : assignment.assignedVariables()) {
    135                if (lastVariable == null || assignment.getIteration(lastVariable) < assignment.getIteration(var)) {
    136                    lastVariable = var;
    137                }
    138            }
    139            if (lastVariable == null) {
    140                sLogger.error("No assignment -> fail");
    141                getSolver().stopSolver();
    142                return false;
    143            }
    144            sLogger.debug("Unassign:" + lastVariable.getName());
    145            Set<T> noGoods = new HashSet<T>();
    146
    147            for (V var : assignment.assignedVariables()) {
    148                if (!var.equals(lastVariable)) {
    149                    noGoods.add(assignment.getValue(var));
    150                }
    151            }
    152            T value = assignment.getValue(lastVariable);
    153
    154            assignment.unassign(iteration, lastVariable);
    155            setNoGood(assignment, value, noGoods);
    156            return false;
    157        }
    158        if (assignment.getValue(variable) != null) {
    159            sLogger.error("Assigned value selected -- not supported by DBT.");
    160            return false;
    161        }
    162        return true;
    163    }
    164
    165    /**
    166     * If no value is selected (because of a dead end), make some unassignments. <br>
    167     * <br>
    168     * If no value is selected (e.g., because the selected variable has all
    169     * values marked as nogood, see {@link DbtValueSelection}),
    170     * <ul>
    171     * <li>compute a union of explanations of all values,
    172     * <ul>
    173     * <li>if it is empty fail (inconsistency is found),
    174     * </ul>
    175     * <li>otherwise pick the last assigned variable from the computed union of
    176     * explanation and unassign it
    177     * <pre>
    178     * (explanation for that is the computed union of explanations without the last assignment).
    179     * </pre>
    180     * </ul>
    181     *
    182     * @see DbtVariableSelection#selectVariable(Solution)
    183     */
    184    @Override
    185    public boolean valueSelected(Assignment<V, T> assignment, long iteration, V variable, T value) {
    186        if (variable != null && value == null) {
    187            Set<T> noGoods = new HashSet<T>();
    188
    189            for (T val : variable.values(assignment)) {
    190                if (noGood(assignment, val) != null) {
    191                    noGoods.addAll(noGood(assignment, val));
    192                }
    193            }
    194            if (noGoods.isEmpty()) {
    195                sLogger.debug("Fail");
    196                getSolver().stopSolver();
    197                return false;
    198            }
    199            V lastVariable = null;
    200
    201            for (T val : noGoods) {
    202                V var = val.variable();
    203
    204                if (lastVariable == null || assignment.getIteration(lastVariable) < assignment.getIteration(var)) {
    205                    lastVariable = var;
    206                }
    207            }
    208            T current = assignment.getValue(lastVariable);
    209
    210            noGoods.remove(current);
    211            assignment.unassign(iteration, lastVariable);
    212            setNoGood(assignment, current, noGoods);
    213        }
    214        return true;
    215    }
    216
    217    @Override
    218    public boolean neighbourSelected(Assignment<V, T> assignment, long iteration, Neighbour<V, T> neighbour) {
    219        return true;
    220    }
    221
    222    @Override
    223    public void neighbourFailed(Assignment<V, T> assignment, long iteration, Neighbour<V, T> neighbour) {
    224    }
    225}