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