001package org.cpsolver.ifs.extension; 002 003import java.util.ArrayList; 004import java.util.HashMap; 005import java.util.HashSet; 006import java.util.Iterator; 007import java.util.List; 008import java.util.Map; 009import java.util.Set; 010 011import org.cpsolver.ifs.assignment.Assignment; 012import org.cpsolver.ifs.assignment.context.AssignmentContext; 013import org.cpsolver.ifs.assignment.context.ExtensionWithContext; 014import org.cpsolver.ifs.model.Constraint; 015import org.cpsolver.ifs.model.Value; 016import org.cpsolver.ifs.model.Variable; 017import org.cpsolver.ifs.solver.Solver; 018import org.cpsolver.ifs.util.DataProperties; 019import org.cpsolver.ifs.util.Progress; 020 021 022/** 023 * Another implementation of MAC propagation. 024 * 025 * @see MacPropagation 026 * 027 * @version IFS 1.3 (Iterative Forward Search)<br> 028 * Copyright (C) 2006 - 2014 Tomas Muller<br> 029 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 030 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 031 * <br> 032 * This library is free software; you can redistribute it and/or modify 033 * it under the terms of the GNU Lesser General Public License as 034 * published by the Free Software Foundation; either version 3 of the 035 * License, or (at your option) any later version. <br> 036 * <br> 037 * This library is distributed in the hope that it will be useful, but 038 * WITHOUT ANY WARRANTY; without even the implied warranty of 039 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 040 * Lesser General Public License for more details. <br> 041 * <br> 042 * You should have received a copy of the GNU Lesser General Public 043 * License along with this library; if not see 044 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 045 * @param <V> Variable 046 * @param <T> Value 047 */ 048 049public class MacRevised<V extends Variable<V, T>, T extends Value<V, T>> extends ExtensionWithContext<V, T, MacRevised<V, T>.NoGood> { 050 private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(MacRevised.class); 051 private boolean iDbt = false; 052 private Progress iProgress; 053 054 /** List of constraints on which arc-consistency is to be maintained */ 055 protected List<Constraint<V, T>> iConstraints = null; 056 /** Current iteration */ 057 protected long iIteration = 0; 058 059 /** Constructor 060 * @param solver current solver 061 * @param properties solver configuration 062 **/ 063 public MacRevised(Solver<V, T> solver, DataProperties properties) { 064 super(solver, properties); 065 iDbt = properties.getPropertyBoolean("MacRevised.Dbt", false); 066 } 067 068 /** Adds a constraint on which arc-consistency is to be maintained 069 * @param constraint a hard constraint to be added 070 **/ 071 public void addConstraint(Constraint<V, T> constraint) { 072 if (iConstraints == null) 073 iConstraints = new ArrayList<Constraint<V, T>>(); 074 iConstraints.add(constraint); 075 } 076 077 /** 078 * Returns true, if arc-consistency is to be maintained on the given 079 * constraint 080 * @param constraint a constraint 081 * @return true if the constraint is in the set 082 */ 083 public boolean contains(Constraint<V, T> constraint) { 084 if (iConstraints == null) 085 return true; 086 return iConstraints.contains(constraint); 087 } 088 089 /** 090 * Before a value is unassigned: until the value is inconsistent with the 091 * current solution, an assignment from its explanation is picked and 092 * unassigned. 093 */ 094 @Override 095 public void beforeAssigned(Assignment<V, T> assignment, long iteration, T value) { 096 if (value == null) 097 return; 098 sLogger.debug("Before assign " + value.variable().getName() + " = " + value.getName()); 099 iIteration = iteration; 100 while (!isGood(assignment, value) && !noGood(assignment, value).isEmpty()) { 101 if (iDbt) 102 sLogger.warn("Going to assign a no-good value " + value + " (noGood:" + noGood(assignment, value) + ")."); 103 T noGoodValue = noGood(assignment, value).iterator().next(); 104 assignment.unassign(iteration, noGoodValue.variable()); 105 } 106 if (!isGood(assignment, value)) { 107 sLogger.warn("Going to assign a bad value " + value + " with empty no-good."); 108 } 109 } 110 111 /** 112 * After a value is assigned: explanations of other values of the value's 113 * variable are reset (to contain only the assigned value), propagation over 114 * the assigned variable takes place. 115 */ 116 @Override 117 public void afterAssigned(Assignment<V, T> assignment, long iteration, T value) { 118 sLogger.debug("After assign " + value.variable().getName() + " = " + value.getName()); 119 iIteration = iteration; 120 if (!isGood(assignment, value)) { 121 sLogger.warn(value.variable().getName() + " = " + value.getName() + " -- not good value assigned (noGood:" + noGood(assignment, value) + ")"); 122 setGood(assignment, value); 123 } 124 125 Set<T> noGood = new HashSet<T>(1); 126 noGood.add(value); 127 List<T> queue = new ArrayList<T>(); 128 for (Iterator<T> i = value.variable().values(assignment).iterator(); i.hasNext();) { 129 T anotherValue = i.next(); 130 if (anotherValue.equals(value) || !isGood(assignment, anotherValue)) 131 continue; 132 setNoGood(assignment, anotherValue, noGood); 133 queue.add(anotherValue); 134 } 135 propagate(assignment, queue); 136 } 137 138 /** 139 * After a value is unassigned: explanations of all values of unassigned 140 * variable are recomputed ({@link Value#conflicts(Assignment)}), propagation undo 141 * over the unassigned variable takes place. 142 */ 143 @Override 144 public void afterUnassigned(Assignment<V, T> assignment, long iteration, T value) { 145 sLogger.debug("After unassign " + value.variable().getName() + " = " + value.getName()); 146 iIteration = iteration; 147 if (!isGood(assignment, value)) 148 sLogger.error(value.variable().getName() + " = " + value.getName() 149 + " -- not good value unassigned (noGood:" + noGood(assignment, value) + ")"); 150 151 List<T> back = new ArrayList<T>(supportValues(assignment, value.variable())); 152 for (T aValue : back) { 153 T current = assignment.getValue(aValue.variable()); 154 if (current != null) { 155 Set<T> noGood = new HashSet<T>(1); 156 noGood.add(current); 157 setNoGood(assignment, aValue, noGood); 158 } else 159 setGood(assignment, aValue); 160 } 161 162 List<T> queue = new ArrayList<T>(); 163 for (T aValue : back) { 164 if (!isGood(assignment, aValue) || revise(assignment, aValue)) 165 queue.add(aValue); 166 } 167 168 propagate(assignment, queue); 169 } 170 171 public void propagate(Assignment<V, T> assignment, List<T> queue) { 172 int idx = 0; 173 while (queue.size() > idx) { 174 T value = queue.get(idx++); 175 sLogger.debug(" -- propagate " + value.variable().getName() + " = " + value.getName() + " (noGood:" 176 + noGood(assignment, value) + ")"); 177 if (goodValues(assignment, value.variable()).isEmpty()) { 178 sLogger.info("Empty domain detected for variable " + value.variable().getName()); 179 continue; 180 } 181 for (Constraint<V, T> constraint : value.variable().hardConstraints()) { 182 if (!contains(constraint)) 183 continue; 184 propagate(assignment, constraint, value, queue); 185 } 186 } 187 } 188 189 public void propagate(Assignment<V, T> assignment, Constraint<V, T> constraint, T noGoodValue, List<T> queue) { 190 for (V aVariable : constraint.variables()) { 191 if (aVariable.equals(noGoodValue.variable())) 192 continue; 193 for (Iterator<T> j = aVariable.values(assignment).iterator(); j.hasNext();) { 194 T aValue = j.next(); 195 if (isGood(assignment, aValue) && constraint.isConsistent(noGoodValue, aValue) 196 && !hasSupport(assignment, constraint, aValue, noGoodValue.variable())) { 197 setNoGood(assignment, aValue, explanation(assignment, constraint, aValue, noGoodValue.variable())); 198 queue.add(aValue); 199 } 200 } 201 } 202 } 203 204 public boolean revise(Assignment<V, T> assignment, T value) { 205 sLogger.debug(" -- revise " + value.variable().getName() + " = " + value.getName()); 206 for (Constraint<V, T> constraint : value.variable().hardConstraints()) { 207 if (!contains(constraint)) 208 continue; 209 if (revise(assignment, constraint, value)) 210 return true; 211 } 212 return false; 213 } 214 215 public boolean revise(Assignment<V, T> assignment, Constraint<V, T> constraint, T value) { 216 for (V aVariable : constraint.variables()) { 217 if (aVariable.equals(value.variable())) 218 continue; 219 if (!hasSupport(assignment, constraint, value, aVariable)) { 220 setNoGood(assignment, value, explanation(assignment, constraint, value, aVariable)); 221 return true; 222 } 223 } 224 return false; 225 } 226 227 public Set<T> explanation(Assignment<V, T> assignment, Constraint<V, T> constraint, T value, V variable) { 228 Set<T> expl = new HashSet<T>(); 229 for (T aValue : variable.values(assignment)) { 230 if (constraint.isConsistent(aValue, value)) { 231 expl.addAll(noGood(assignment, aValue)); 232 } 233 } 234 return expl; 235 } 236 237 public Set<T> supports(Assignment<V, T> assignment, Constraint<V, T> constraint, T value, V variable) { 238 Set<T> sup = new HashSet<T>(); 239 for (T aValue : variable.values(assignment)) { 240 if (!isGood(assignment, aValue)) 241 continue; 242 if (!constraint.isConsistent(aValue, value)) 243 continue; 244 sup.add(aValue); 245 } 246 return sup; 247 } 248 249 public boolean hasSupport(Assignment<V, T> assignment, Constraint<V, T> constraint, T value, V variable) { 250 for (T aValue : variable.values(assignment)) { 251 if (isGood(assignment, aValue) && constraint.isConsistent(aValue, value)) { 252 // sLogger.debug(" -- "+variable.getName()+" = "+aValue.getName()+" supports " 253 // + 254 // value.variable().getName()+" = "+value.getName()+" (constraint:"+constraint.getName()+")"); 255 return true; 256 } 257 } 258 // sLogger.debug(" -- value "+value.variable().getName()+" = " + 259 // value.getName()+" has no support from values of variable "+variable.getName()+" (constraint:"+constraint.getName()+")"); 260 /* 261 * for (Enumeration e=variable.values().elements();e.hasMoreElements();) 262 * { T aValue = (T)e.nextElement(); if 263 * (constraint.isConsistent(aValue,value)) { 264 * //sLogger.debug(" -- support " 265 * +aValue.getName()+" is not good: "+expl2str(noGood(aValue))); } } 266 */ 267 return false; 268 } 269 270 /** 271 * Initialization. Enforce arc-consistency over the current (initial) 272 * solution. AC3 algorithm is used. 273 */ 274 @Override 275 public boolean init(Solver<V, T> solver) { 276 return true; 277 } 278 279 /** support values of a variable */ 280 @SuppressWarnings("unchecked") 281 private Set<T> supportValues(Assignment<V, T> assignment, V variable) { 282 Set<T>[] ret = getContext(assignment).getNoGood(variable); 283 if (ret == null) { 284 ret = new Set[] { new HashSet<T>(1000), new HashSet<T>() }; 285 getContext(assignment).setNoGood(variable, ret); 286 } 287 return ret[0]; 288 } 289 290 /** good values of a variable (values not removed from variables domain) 291 * @param assignment current assignment 292 * @param variable given variable 293 * @return good values for the variable (i.e., values from the domain of the variable that have no no-good set) 294 **/ 295 @SuppressWarnings("unchecked") 296 public Set<T> goodValues(Assignment<V, T> assignment, V variable) { 297 Set<T>[] ret = getContext(assignment).getNoGood(variable); 298 if (ret == null) { 299 ret = new Set[] { new HashSet<T>(1000), new HashSet<T>() }; 300 getContext(assignment).setNoGood(variable, ret); 301 } 302 return ret[1]; 303 } 304 305 /** notification that a no-good value becomes good or vice versa */ 306 private void goodnessChanged(Assignment<V, T> assignment, T value) { 307 if (isGood(assignment, value)) { 308 goodValues(assignment, value.variable()).add(value); 309 } else { 310 goodValues(assignment, value.variable()).remove(value); 311 } 312 } 313 314 /** removes support of a variable */ 315 private void removeSupport(Assignment<V, T> assignment, V variable, T value) { 316 supportValues(assignment, variable).remove(value); 317 } 318 319 /** adds support of a variable */ 320 private void addSupport(Assignment<V, T> assignment, V variable, T value) { 321 supportValues(assignment, variable).add(value); 322 } 323 324 /** variables explanation 325 * @param assignment current assignment 326 * @param value given value 327 * @return no-good set for the value 328 **/ 329 public Set<T> noGood(Assignment<V, T> assignment, T value) { 330 return getContext(assignment).getNoGood(value); 331 } 332 333 /** is variable good 334 * @param assignment current assignment 335 * @param value given value 336 * @return true if good, i.e., the value has no no-good set 337 **/ 338 public boolean isGood(Assignment<V, T> assignment, T value) { 339 return (getContext(assignment).getNoGood(value) == null); 340 } 341 342 /** sets value to be good 343 * @param assignment current assignment 344 * @param value given value 345 **/ 346 protected void setGood(Assignment<V, T> assignment, T value) { 347 sLogger.debug(" -- set good " + value.variable().getName() + " = " + value.getName()); 348 Set<T> noGood = noGood(assignment, value); 349 if (noGood != null) 350 for (T v : noGood) 351 removeSupport(assignment, v.variable(), value); 352 getContext(assignment).setNoGood(value, null); 353 goodnessChanged(assignment, value); 354 } 355 356 /** sets values explanation (initialization) */ 357 private void initNoGood(Assignment<V, T> assignment, T value, Set<T> reason) { 358 getContext(assignment).setNoGood(value, reason); 359 } 360 361 private String expl2str(Set<T> expl) { 362 StringBuffer sb = new StringBuffer("["); 363 for (Iterator<T> i = expl.iterator(); i.hasNext();) { 364 T value = i.next(); 365 sb.append(value.variable().getName() + "=" + value.getName()); 366 if (i.hasNext()) 367 sb.append(", "); 368 } 369 sb.append("]"); 370 return sb.toString(); 371 } 372 373 private void checkExpl(Assignment<V, T> assignment, Set<T> expl) { 374 sLogger.debug(" -- checking explanation: " + expl2str(expl)); 375 for (Iterator<T> i = expl.iterator(); i.hasNext();) { 376 T value = i.next(); 377 T current = assignment.getValue(value.variable()); 378 if (!value.equals(current)) { 379 if (current == null) 380 sLogger.warn(" -- variable " + value.variable().getName() + " unassigned"); 381 else 382 sLogger.warn(" -- variable " + value.variable().getName() + " assigned to a different value " + current.getName()); 383 } 384 } 385 } 386 387 private void printAssignments(Assignment<V, T> assignment) { 388 sLogger.debug(" -- printing assignments: "); 389 for (Iterator<V> i = getModel().variables().iterator(); i.hasNext();) { 390 V variable = i.next(); 391 T value = assignment.getValue(variable); 392 if (value != null) 393 sLogger.debug(" -- " + variable.getName() + " = " + value.getName()); 394 } 395 } 396 397 /** sets value's explanation 398 * @param assignment current assignment 399 * @param value a value 400 * @param reason no-good set for the value 401 **/ 402 public void setNoGood(Assignment<V, T> assignment, T value, Set<T> reason) { 403 sLogger.debug(" -- set nogood " + value.variable().getName() + " = " + value.getName() + "(expl:" + expl2str(reason) + ")"); 404 if (value.equals(assignment.getValue(value.variable()))) { 405 try { 406 throw new Exception("An assigned value " + value.variable().getName() + " = " + value.getName() + " become no good (noGood:" + reason + ")!!"); 407 } catch (Exception e) { 408 sLogger.warn(e.getMessage(), e); 409 } 410 checkExpl(assignment, reason); 411 printAssignments(assignment); 412 } 413 Set<T> noGood = noGood(assignment, value); 414 if (noGood != null) 415 for (T v : noGood) 416 removeSupport(assignment, v.variable(), value); 417 getContext(assignment).setNoGood(value, reason); 418 for (T aValue : reason) { 419 addSupport(assignment, aValue.variable(), value); 420 } 421 goodnessChanged(assignment, value); 422 } 423 424 @Override 425 public NoGood createAssignmentContext(Assignment<V, T> assignment) { 426 return new NoGood(assignment); 427 } 428 429 /** 430 * Assignment context 431 */ 432 public class NoGood implements AssignmentContext { 433 private Map<V, Set<T>[]> iNoGood = new HashMap<V, Set<T>[]>(); 434 private Map<V, Map<T, Set<T>>> iNoGoodVal = new HashMap<V, Map<T, Set<T>>>(); 435 436 public NoGood(Assignment<V, T> assignment) { 437 iProgress = Progress.getInstance(getModel()); 438 iProgress.save(); 439 iProgress.setPhase("Initializing propagation:", getModel().variables().size()); 440 for (Iterator<V> i = getModel().variables().iterator(); i.hasNext();) { 441 V aVariable = i.next(); 442 supportValues(assignment, aVariable).clear(); 443 goodValues(assignment, aVariable).clear(); 444 } 445 List<T> queue = new ArrayList<T>(); 446 for (Iterator<V> i = getModel().variables().iterator(); i.hasNext();) { 447 V aVariable = i.next(); 448 for (Iterator<T> j = aVariable.values(assignment).iterator(); j.hasNext();) { 449 T aValue = j.next(); 450 initNoGood(assignment, aValue, null); 451 goodValues(assignment, aVariable).add(aValue); 452 T current = assignment.getValue(aVariable); 453 if (revise(assignment, aValue)) { 454 queue.add(aValue); 455 } else if (current != null && !aValue.equals(current)) { 456 Set<T> noGood = new HashSet<T>(); 457 noGood.add(current); 458 MacRevised.this.setNoGood(assignment, aValue, noGood); 459 queue.add(aValue); 460 } 461 } 462 iProgress.incProgress(); 463 } 464 propagate(assignment, queue); 465 iProgress.restore(); 466 } 467 468 public Set<T>[] getNoGood(V variable) { 469 return iNoGood.get(variable); 470 } 471 472 public void setNoGood(V variable, Set<T>[] noGood) { 473 if (noGood == null) 474 iNoGood.remove(variable); 475 else 476 iNoGood.put(variable, noGood); 477 } 478 479 public Set<T> getNoGood(T value) { 480 Map<T, Set<T>> ng = iNoGoodVal.get(value.variable()); 481 if (ng == null) return null; 482 return ng.get(value); 483 } 484 485 public void setNoGood(T value, Set<T> noGood) { 486 Map<T, Set<T>> ng = iNoGoodVal.get(value.variable()); 487 if (ng == null) { 488 ng = new HashMap<T, Set<T>>(); 489 iNoGoodVal.put(value.variable(), ng); 490 } 491 if (noGood == null) 492 ng.remove(value); 493 else 494 ng.put(value, noGood); 495 } 496 } 497}