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}