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