001package net.sf.cpsolver.ifs.extension; 002 003import java.util.ArrayList; 004import java.util.Collection; 005import java.util.HashSet; 006import java.util.HashMap; 007import java.util.Iterator; 008import java.util.LinkedList; 009import java.util.List; 010import java.util.Map; 011import java.util.Queue; 012import java.util.Set; 013 014import net.sf.cpsolver.ifs.model.Constraint; 015import net.sf.cpsolver.ifs.model.Value; 016import net.sf.cpsolver.ifs.model.Variable; 017import net.sf.cpsolver.ifs.solver.Solver; 018import net.sf.cpsolver.ifs.util.DataProperties; 019import 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 Tomáš Müller<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 */ 100public 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}