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