001 package net.sf.cpsolver.ifs.dbt;
002
003 import java.util.HashSet;
004 import java.util.Set;
005
006 import net.sf.cpsolver.ifs.extension.MacPropagation;
007 import net.sf.cpsolver.ifs.model.Neighbour;
008 import net.sf.cpsolver.ifs.model.Value;
009 import net.sf.cpsolver.ifs.model.Variable;
010 import net.sf.cpsolver.ifs.solution.Solution;
011 import net.sf.cpsolver.ifs.solver.Solver;
012 import net.sf.cpsolver.ifs.solver.SolverListener;
013 import 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 Tomas Muller<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 */
045 public 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 }