001 package net.sf.cpsolver.ifs.extension;
002
003
004 import java.util.*;
005
006 import net.sf.cpsolver.ifs.model.*;
007 import net.sf.cpsolver.ifs.solver.*;
008 import net.sf.cpsolver.ifs.util.*;
009
010 /**
011 * MAC propagation.
012 * <br><br>
013 * During the arc consistency maintenance, when a value is deleted from a variable’s domain, the reason (forming an
014 * explanation) can be computed and attached to the deleted value. Once a variable (say Vx with the assigned value vx)
015 * is unassigned during the search, all deleted values which contain a pair Vx = vx in their explanations need to be
016 * recomputed. Such value can be either still inconsistent with the current (partial) solution (a different explanation
017 * is attached to it in this case) or it can be returned back to its variable's domain. Arc consistency is maintained
018 * after each iteration step, i.e., the selected assignment is propagated into the not yet assigned variables. When a
019 * value vx is assigned to a variable Vx, an explanation Vx != vx' ← Vx = vx is attached to all values vx' of the
020 * variable Vx, different from vx.
021 * <br><br>
022 * In the case of forward checking (only constraints going from assigned variables to unassigned variables are revised),
023 * computing explanations is rather easy. A value vx is deleted from the domain of the variable Vx only if there is a
024 * constraint which prohibits the assignment Vx=vx because of the existing assignments (e.g., Vy = vy, … Vz = vz).
025 * An explanation for the deletion of this value vx is then Vx != vx ← (Vy = vy & ... Vz = vz), where Vy = vy & ... Vz = vz
026 * are assignments contained in the prohibiting constraint. In case of arc consistency, a value vx is deleted from
027 * the domain of the variable Vx if there is a constraint which does not permit the assignment Vx = vx with other
028 * possible assignments of the other variables in the constraint. This means that there is no support value (or
029 * combination of values) for the value vx of the variable Vx in the constraint. An explanation is then a union of
030 * explanations of all possible support values for the assignment Vx = vx of this constraint which were deleted.
031 * The reason is that if one of these support values is returned to its variable's domain, this value vx may
032 * be returned as well (i.e., the reason for its deletion has vanished, a new reason needs to be computed).
033 * <br><br>
034 * As for the implementation, we only need to enforce arc consistency of the initial solution and to extend unassign
035 * and assign methods. Procedure {@link MacPropagation#afterAssigned(long, Value)} enforces arc consistency of the
036 * solution with the selected assignment variable = value and the procedure {@link MacPropagation#afterUnassigned(long, Value)}
037 * "undoes" the assignment variable = value. It means that explanations of all values which were deleted and which
038 * contain assignment variable = value in their explanations need to be recomputed. This can be done via returning
039 * all these values into their variables’ domains followed by arc consistency maintenance over their variables.
040 * <br><br>
041 * Parameters:
042 * <table border='1'><tr><th>Parameter</th><th>Type</th><th>Comment</th></tr>
043 * <tr><td>MacPropagation.JustForwardCheck</td><td>{@link Boolean}</td><td>If true, only forward checking instead of full arc consistency is maintained during the search.</td></tr>
044 * </table>
045 *
046 * @version
047 * IFS 1.1 (Iterative Forward Search)<br>
048 * Copyright (C) 2006 Tomáš Müller<br>
049 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
050 * Lazenska 391, 76314 Zlin, Czech Republic<br>
051 * <br>
052 * This library is free software; you can redistribute it and/or
053 * modify it under the terms of the GNU Lesser General Public
054 * License as published by the Free Software Foundation; either
055 * version 2.1 of the License, or (at your option) any later version.
056 * <br><br>
057 * This library is distributed in the hope that it will be useful,
058 * but WITHOUT ANY WARRANTY; without even the implied warranty of
059 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
060 * Lesser General Public License for more details.
061 * <br><br>
062 * You should have received a copy of the GNU Lesser General Public
063 * License along with this library; if not, write to the Free Software
064 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
065 */
066 public class MacPropagation extends Extension {
067 private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(MacPropagation.class);
068 private boolean iJustForwardCheck = false;
069 private Progress iProgress;
070
071 /** List of constraints on which arc-consistency is to be maintained */
072 protected Vector iConstraints = null;
073 /** Current iteration */
074 protected long iIteration = 0;
075
076 /** Constructor */
077 public MacPropagation(Solver solver, DataProperties properties) {
078 super(solver, properties);
079 iJustForwardCheck = properties.getPropertyBoolean("MacPropagation.JustForwardCheck", false);
080 }
081
082 /** Adds a constraint on which arc-consistency is to be maintained */
083 public void addConstraint(Constraint constraint) {
084 if (iConstraints == null) iConstraints = new FastVector();
085 iConstraints.addElement(constraint);
086 }
087
088 /** Returns true, if arc-consistency is to be maintained on the given constraint */
089 public boolean contains(Constraint constraint) {
090 if (iConstraints == null) return true;
091 return iConstraints.contains(constraint);
092 }
093
094 /** Before a value is unassigned: until the value is inconsistent with the current solution,
095 * an assignment from its explanation is picked and unassigned.
096 */
097 public void beforeAssigned(long iteration, Value value) {
098 iIteration = iteration;
099 if (value == null) return;
100 if (!isGood(value)) {
101 while (!isGood(value) && !noGood(value).isEmpty()) {
102 Value noGoodValue = (Value)noGood(value).iterator().next();
103 noGoodValue.variable().unassign(iteration);
104 }
105 }
106 if (!isGood(value)) {
107 sLogger.warn("Going to assign a bad value "+value+" with empty no-good.");
108 }
109 }
110
111 /** After a value is assigned: explanations of other values of the value's variable are reset (to contain only the assigned value),
112 * propagation over the assigned variable takes place.
113 */
114 public void afterAssigned(long iteration, Value value) {
115 iIteration = iteration;
116 if (!isGood(value)) {
117 sLogger.warn(value.variable().getName() + " = " + value.getName() + " -- not good value assigned (noGood:" + noGood(value) + ")");
118 setGood(value);
119 }
120
121 HashSet noGood = new HashSet(1);
122 noGood.add(value);
123 for (Enumeration i = value.variable().values().elements(); i.hasMoreElements(); ) {
124 Value anotherValue = (Value)i.nextElement();
125 if (anotherValue.equals(value)) continue;
126 setNoGood(anotherValue, noGood);
127 }
128 propagate(value.variable());
129 }
130
131 /** After a value is unassigned: explanations of all values of unassigned variable are recomputed ({@link Value#conflicts()}), propagation
132 * undo over the unassigned variable takes place.
133 */
134 public void afterUnassigned(long iteration, Value value) {
135 iIteration = iteration;
136 if (!isGood(value))
137 sLogger.error(value.variable().getName() + " = " + value.getName() + " -- not good value unassigned (noGood:" + noGood(value) + ")");
138 for (Enumeration i = value.variable().values().elements(); i.hasMoreElements(); ) {
139 Value anotherValue = (Value)i.nextElement();
140 if (!isGood(anotherValue)) {
141 Set noGood = anotherValue.conflicts();
142 if (noGood == null)
143 setGood(anotherValue);
144 else
145 setNoGood(anotherValue, noGood);
146 }
147 }
148 undoPropagate(value.variable());
149 }
150
151 /** Initialization. Enforce arc-consistency over the current (initial) solution. AC3 algorithm is used. */
152 public boolean init(Solver solver) {
153 boolean isOk = true;
154 iProgress = Progress.getInstance(getModel());
155 iProgress.save();
156 iProgress.setPhase("Initializing propagation:", 3 * getModel().variables().size());
157 for (Enumeration i1 = getModel().variables().elements(); i1.hasMoreElements(); ) {
158 Variable aVariable = (Variable)i1.nextElement();
159 supportValues(aVariable).clear();
160 goodValues(aVariable).clear();
161 }
162 for (Enumeration i1 = getModel().variables().elements(); i1.hasMoreElements(); ) {
163 Variable aVariable = (Variable)i1.nextElement();
164 for (Enumeration i2 = aVariable.values().elements(); i2.hasMoreElements(); ) {
165 Value aValue = (Value)i2.nextElement();
166 Set noGood = aValue.conflicts();
167 initNoGood(aValue, noGood);
168 if (noGood == null) {
169 goodValues(aVariable).add(aValue);
170 }
171 else {
172 }
173 }
174 iProgress.incProgress();
175 }
176 net.sf.cpsolver.ifs.util.Queue queue = new net.sf.cpsolver.ifs.util.Queue(getModel().variables().size() + 1);
177 for (Enumeration i1 = getModel().variables().elements(); i1.hasMoreElements(); ) {
178 Variable aVariable = (Variable)i1.nextElement();
179 for (Enumeration i2 = aVariable.hardConstraints().elements(); i2.hasMoreElements(); ) {
180 Constraint constraint = (Constraint)i2.nextElement();
181 propagate(constraint, aVariable, queue);
182 }
183 iProgress.incProgress();
184 }
185 if (!iJustForwardCheck)
186 propagate(queue);
187 for (Enumeration i1 = getModel().variables().elements(); i1.hasMoreElements(); ) {
188 Variable aVariable = (Variable)i1.nextElement();
189 Vector values2delete = new FastVector();
190 for (Enumeration i2 = aVariable.values().elements(); i2.hasMoreElements(); ) {
191 Value aValue = (Value)i2.nextElement();
192 if (!isGood(aValue) && noGood(aValue).isEmpty()) {
193 values2delete.addElement(aValue);
194 }
195 }
196 Object[] vals = values2delete.toArray();
197 for (int i = 0; i < vals.length; i++)
198 aVariable.removeValue(0, (Value)vals[i]);
199 if (aVariable.values().isEmpty()) {
200 sLogger.error(aVariable.getName() + " has empty domain!");
201 isOk = false;
202 }
203 iProgress.incProgress();
204 }
205 iProgress.restore();
206 return isOk;
207 }
208
209 /** Propagation over the given variable. */
210 protected void propagate(Variable variable) {
211 net.sf.cpsolver.ifs.util.Queue queue = new net.sf.cpsolver.ifs.util.Queue(variable.getModel().variables().size() + 1);
212 if (variable.getAssignment() != null) {
213 for (Enumeration i = variable.hardConstraints().elements(); i.hasMoreElements(); ) {
214 Constraint constraint = (Constraint)i.nextElement();
215 if (contains(constraint))
216 propagate(constraint, variable.getAssignment(), queue);
217 }
218 }
219 else {
220 for (Enumeration i = variable.hardConstraints().elements(); i.hasMoreElements(); ) {
221 Constraint constraint = (Constraint)i.nextElement();
222 if (contains(constraint))
223 propagate(constraint, variable, queue);
224 }
225 }
226 if (!iJustForwardCheck && !queue.isEmpty())
227 propagate(queue);
228 }
229
230 /** Propagation over the queue of variables. */
231 protected void propagate(net.sf.cpsolver.ifs.util.Queue queue) {
232 while (!queue.isEmpty()) {
233 Variable aVariable = (Variable)queue.get();
234 for (Enumeration i = aVariable.hardConstraints().elements(); i.hasMoreElements(); ) {
235 Constraint constraint = (Constraint)i.nextElement();
236 if (contains(constraint))
237 propagate(constraint, aVariable, queue);
238 }
239 }
240 }
241
242 /** Propagation undo over the given variable. All values having given variable in thair explanations needs to be
243 * recomputed. This is done in two phases:
244 * 1) values that contain this variable in explanation are returned back to domains (marked as good)
245 * 2) propagation over variables which contains a value that was marked as good takes place
246 */
247 public void undoPropagate(Variable variable) {
248 Hashtable undoVars = new Hashtable();
249 while (!supportValues(variable).isEmpty()) {
250 Value value = (Value)supportValues(variable).iterator().next();
251 Set noGood = value.conflicts();
252 if (noGood == null) {
253 setGood(value);
254 Vector values = (Vector)undoVars.get(value.variable());
255 if (values == null) {
256 values = new FastVector();
257 undoVars.put(value.variable(), values);
258 }
259 values.addElement(value);
260 }
261 else {
262 setNoGood(value, noGood);
263 if (noGood.isEmpty())
264 ((Variable)value.variable()).removeValue(iIteration, value);
265 }
266 }
267
268 net.sf.cpsolver.ifs.util.Queue queue = new net.sf.cpsolver.ifs.util.Queue(variable.getModel().variables().size() + 1);
269 for (Enumeration e = undoVars.keys(); e.hasMoreElements();) {
270 Variable aVariable = (Variable)e.nextElement();
271 Vector values = (Vector)undoVars.get(aVariable);
272 boolean add = false;
273 for (Enumeration e1 = aVariable.constraintVariables().keys(); e1.hasMoreElements(); )
274 if (propagate((Variable)e1.nextElement(), aVariable, values))
275 add = true;
276 if (add)
277 queue.put(aVariable);
278 }
279 for (Enumeration e1 = variable.constraintVariables().keys(); e1.hasMoreElements(); )
280 if (propagate((Variable)e1.nextElement(), variable) && !queue.contains(variable))
281 queue.put(variable);
282 if (!iJustForwardCheck)
283 propagate(queue);
284 }
285
286 protected boolean propagate(Variable aVariable, Variable anotherVariable, Vector adepts) {
287 if (goodValues(aVariable).isEmpty())
288 return false;
289 boolean ret = false;
290 Vector conflicts = null;
291 for (Enumeration i = ((Vector)anotherVariable.constraintVariables().get(aVariable)).elements(); i.hasMoreElements();) {
292 Constraint constraint = (Constraint)i.nextElement();
293 for (Iterator i1 = goodValues(aVariable).iterator(); i1.hasNext();) {
294 Value aValue = (Value)i1.next();
295 if (conflicts == null)
296 conflicts = conflictValues(constraint, aValue, adepts);
297 else
298 conflicts = conflictValues(constraint, aValue, conflicts);
299 if (conflicts == null || conflicts.isEmpty())
300 break;
301 }
302 if (conflicts != null && !conflicts.isEmpty())
303 for (Enumeration i1 = conflicts.elements(); i1.hasMoreElements();) {
304 Value conflictValue = (Value)i1.nextElement();
305 Set reason = reason(constraint, aVariable, conflictValue);
306 //sLogger.debug(" "+conflictValue+" become nogood (c:"+constraint.getName()+", r:"+reason+")");
307 setNoGood(conflictValue, reason);
308 adepts.removeElement(conflictValue);
309 if (reason.isEmpty())
310 ((Variable)conflictValue.variable()).removeValue(iIteration,conflictValue);
311 ret = true;
312 }
313 }
314 return ret;
315 }
316
317 protected boolean propagate(Variable aVariable, Variable anotherVariable) {
318 if (goodValues(anotherVariable).isEmpty())
319 return false;
320 return propagate(aVariable, anotherVariable, new FastVector(goodValues(anotherVariable)));
321 }
322
323 /** support values of a variable */
324 private Set supportValues(Variable variable) {
325 Set[] ret = (Set[])variable.getExtra();
326 if (ret == null) {
327 ret = new HashSet[] { new HashSet(1000), new HashSet()};
328 variable.setExtra(ret);
329 }
330 return ret[0];
331 }
332
333 /** good values of a variable (values not removed from variables domain)*/
334 public Set goodValues(Variable variable) {
335 Set[] ret = (Set[])variable.getExtra();
336 if (ret == null) {
337 ret = new HashSet[] { new HashSet(1000), new HashSet()};
338 variable.setExtra(ret);
339 }
340 return ret[1];
341 }
342
343 /** notification that a nogood value becomes good or vice versa */
344 private void goodnessChanged(Value value) {
345 if (isGood(value)) {
346 goodValues(value.variable()).add(value);
347 }
348 else {
349 goodValues(value.variable()).remove(value);
350 }
351 }
352 /** removes support of a variable */
353 private void removeSupport(Variable variable, Value value) {
354 supportValues(variable).remove(value);
355 }
356 /** adds support of a variable */
357 private void addSupport(Variable variable, Value value) {
358 supportValues(variable).add(value);
359 }
360
361 /** variables explanation */
362 public Set noGood(Value value) {
363 return (Set)value.getExtra();
364 }
365 /** is variable good */
366 public boolean isGood(Value value) {
367 return (value.getExtra() == null);
368 }
369 /** sets value to be good */
370 protected void setGood(Value value) {
371 Set noGood = noGood(value);
372 if (noGood != null)
373 for (Iterator i = noGood.iterator(); i.hasNext();)
374 removeSupport(((Value)i.next()).variable(), value);
375 value.setExtra(null);
376 goodnessChanged(value);
377 }
378 /** sets values explanation (initialization) */
379 private void initNoGood(Value value, Set reason) {
380 value.setExtra(reason);
381 }
382 /** sets value's explanation*/
383 public void setNoGood(Value value, Set reason) {
384 Set noGood = noGood(value);
385 if (noGood != null)
386 for (Iterator i = noGood.iterator(); i.hasNext();)
387 removeSupport(((Value)i.next()).variable(), value);
388 value.setExtra(reason);
389 for (Iterator i = reason.iterator(); i.hasNext();) {
390 Value aValue = (Value)i.next();
391 addSupport(aValue.variable(), value);
392 }
393 goodnessChanged(value);
394 }
395
396 /** propagation over a constraint */
397 private void propagate(Constraint constraint, Value anAssignedValue, net.sf.cpsolver.ifs.util.Queue queue) {
398 HashSet reason = new HashSet(1);
399 reason.add(anAssignedValue);
400 Collection conflicts = conflictValues(constraint, anAssignedValue);
401 if (conflicts != null && !conflicts.isEmpty())
402 for (Iterator i1 = conflicts.iterator(); i1.hasNext();) {
403 Value conflictValue = (Value)i1.next();
404 //sLogger.debug(" "+conflictValue+" become nogood (c:"+constraint.getName()+", r:"+reason+")");
405 setNoGood(conflictValue, reason);
406 if (!queue.contains(conflictValue.variable()))
407 queue.put(conflictValue.variable());
408 }
409 }
410
411 /** propagation over a constraint */
412 private void propagate(Constraint constraint, Variable aVariable, net.sf.cpsolver.ifs.util.Queue queue) {
413 if (goodValues(aVariable).isEmpty())
414 return;
415 Vector conflicts = conflictValues(constraint, aVariable);
416
417 if (conflicts != null && !conflicts.isEmpty()) {
418 for (Enumeration i1 = conflicts.elements(); i1.hasMoreElements(); ) {
419 Value conflictValue = (Value)i1.nextElement();
420 if (!queue.contains(conflictValue.variable()))
421 queue.put(conflictValue.variable());
422 Set reason = reason(constraint, aVariable, conflictValue);
423 //sLogger.debug(" "+conflictValue+" become nogood (c:"+constraint.getName()+", r:"+reason+")");
424 setNoGood(conflictValue, reason);
425 if (reason.isEmpty())
426 ((Variable)conflictValue.variable()).removeValue(iIteration, conflictValue);
427 }
428 }
429 }
430
431 private Vector conflictValues(Constraint constraint, Value aValue) {
432 Vector ret = new FastVector();
433
434 for (Enumeration i1 = constraint.variables().elements(); i1.hasMoreElements();) {
435 Variable variable = (Variable)i1.nextElement();
436 if (variable.equals(aValue.variable()))
437 continue;
438 if (variable.getAssignment() != null)
439 continue;
440
441 for (Iterator i2 = goodValues(variable).iterator();i2.hasNext();) {
442 Value value = (Value)i2.next();
443 if (!constraint.isConsistent(aValue, value))
444 ret.addElement(value);
445 }
446 }
447 return ret;
448 }
449
450 private Vector conflictValues(Constraint constraint, Value aValue, Vector values) {
451 Vector ret = new FastVector(values.size());
452
453 for (Enumeration i1 = values.elements(); i1.hasMoreElements();) {
454 Value value = (Value)i1.nextElement();
455 if (!constraint.isConsistent(aValue, value))
456 ret.addElement(value);
457 }
458 return ret;
459 }
460
461 private Vector conflictValues(Constraint constraint, Variable aVariable) {
462 Vector conflicts = null;
463 for (Iterator i1 = goodValues(aVariable).iterator(); i1.hasNext();) {
464 Value aValue = (Value)i1.next();
465 if (conflicts == null)
466 conflicts = conflictValues(constraint, aValue);
467 else
468 conflicts = conflictValues(constraint, aValue, conflicts);
469 if (conflicts == null || conflicts.isEmpty())
470 return null;
471 }
472 return conflicts;
473 }
474
475 private HashSet reason(Constraint constraint, Variable aVariable, Value aValue) {
476 HashSet ret = new HashSet();
477 for (Enumeration i1 = aVariable.values().elements(); i1.hasMoreElements();) {
478 Value value = (Value)i1.nextElement();
479 if (constraint.isConsistent(aValue, value)) {
480 if (noGood(value) == null)
481 sLogger.error("Something went wrong: value " + value + " cannot participate in a reason.");
482 else
483 ret.addAll(noGood(value));
484 }
485 }
486 return ret;
487 }
488
489 }