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}