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