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