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 Tomáš Müller<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 NoGood context = getContext(assignment); 101 while (!context.isGood(value) && !context.noGood(value).isEmpty()) { 102 if (iDbt) 103 sLogger.warn("Going to assign a no-good value " + value + " (noGood:" + context.noGood(value) + ")."); 104 T noGoodValue = context.noGood(value).iterator().next(); 105 assignment.unassign(iteration, noGoodValue.variable()); 106 } 107 if (!context.isGood(value)) { 108 sLogger.warn("Going to assign a bad value " + value + " with empty no-good."); 109 } 110 } 111 112 /** 113 * After a value is assigned: explanations of other values of the value's 114 * variable are reset (to contain only the assigned value), propagation over 115 * the assigned variable takes place. 116 */ 117 @Override 118 public void afterAssigned(Assignment<V, T> assignment, long iteration, T value) { 119 sLogger.debug("After assign " + value.variable().getName() + " = " + value.getName()); 120 iIteration = iteration; 121 NoGood context = getContext(assignment); 122 if (!context.isGood(value)) { 123 sLogger.warn(value.variable().getName() + " = " + value.getName() + " -- not good value assigned (noGood:" + context.noGood(value) + ")"); 124 context.setGood(value); 125 } 126 127 Set<T> noGood = new HashSet<T>(1); 128 noGood.add(value); 129 List<T> queue = new ArrayList<T>(); 130 for (Iterator<T> i = value.variable().values(assignment).iterator(); i.hasNext();) { 131 T anotherValue = i.next(); 132 if (anotherValue.equals(value) || !context.isGood(anotherValue)) 133 continue; 134 context.setNoGood(anotherValue, noGood); 135 queue.add(anotherValue); 136 } 137 context.propagate(assignment, queue); 138 } 139 140 /** 141 * After a value is unassigned: explanations of all values of unassigned 142 * variable are recomputed ({@link Value#conflicts(Assignment)}), propagation undo 143 * over the unassigned variable takes place. 144 */ 145 @Override 146 public void afterUnassigned(Assignment<V, T> assignment, long iteration, T value) { 147 sLogger.debug("After unassign " + value.variable().getName() + " = " + value.getName()); 148 iIteration = iteration; 149 NoGood context = getContext(assignment); 150 if (!context.isGood(value)) 151 sLogger.error(value.variable().getName() + " = " + value.getName() + " -- not good value unassigned (noGood:" + context.noGood(value) + ")"); 152 153 List<T> back = new ArrayList<T>(context.supportValues(value.variable())); 154 for (T aValue : back) { 155 T current = assignment.getValue(aValue.variable()); 156 if (current != null) { 157 Set<T> noGood = new HashSet<T>(1); 158 noGood.add(current); 159 context.setNoGood(aValue, noGood); 160 } else 161 context.setGood(aValue); 162 } 163 164 List<T> queue = new ArrayList<T>(); 165 for (T aValue : back) { 166 if (!context.isGood(aValue) || context.revise(assignment, aValue)) 167 queue.add(aValue); 168 } 169 170 context.propagate(assignment, queue); 171 } 172 173 /** 174 * Initialization. Enforce arc-consistency over the current (initial) 175 * solution. AC3 algorithm is used. 176 */ 177 @Override 178 public boolean init(Solver<V, T> solver) { 179 return true; 180 } 181 182 private String expl2str(Set<T> expl) { 183 StringBuffer sb = new StringBuffer("["); 184 for (Iterator<T> i = expl.iterator(); i.hasNext();) { 185 T value = i.next(); 186 sb.append(value.variable().getName() + "=" + value.getName()); 187 if (i.hasNext()) 188 sb.append(", "); 189 } 190 sb.append("]"); 191 return sb.toString(); 192 } 193 194 private void checkExpl(Assignment<V, T> assignment, Set<T> expl) { 195 sLogger.debug(" -- checking explanation: " + expl2str(expl)); 196 for (Iterator<T> i = expl.iterator(); i.hasNext();) { 197 T value = i.next(); 198 T current = assignment.getValue(value.variable()); 199 if (!value.equals(current)) { 200 if (current == null) 201 sLogger.warn(" -- variable " + value.variable().getName() + " unassigned"); 202 else 203 sLogger.warn(" -- variable " + value.variable().getName() + " assigned to a different value " + current.getName()); 204 } 205 } 206 } 207 208 private void printAssignments(Assignment<V, T> assignment) { 209 sLogger.debug(" -- printing assignments: "); 210 for (Iterator<V> i = getModel().variables().iterator(); i.hasNext();) { 211 V variable = i.next(); 212 T value = assignment.getValue(variable); 213 if (value != null) 214 sLogger.debug(" -- " + variable.getName() + " = " + value.getName()); 215 } 216 } 217 218 @Override 219 public NoGood createAssignmentContext(Assignment<V, T> assignment) { 220 return new NoGood(assignment); 221 } 222 223 /** 224 * Assignment context 225 */ 226 public class NoGood implements AssignmentContext { 227 private Map<V, Set<T>[]> iNoGood = new HashMap<V, Set<T>[]>(); 228 private Map<V, Map<T, Set<T>>> iNoGoodVal = new HashMap<V, Map<T, Set<T>>>(); 229 230 public NoGood(Assignment<V, T> assignment) { 231 iProgress = Progress.getInstance(getModel()); 232 iProgress.save(); 233 iProgress.setPhase("Initializing propagation:", getModel().variables().size()); 234 for (Iterator<V> i = getModel().variables().iterator(); i.hasNext();) { 235 V aVariable = i.next(); 236 supportValues(aVariable).clear(); 237 goodValues(aVariable).clear(); 238 } 239 List<T> queue = new ArrayList<T>(); 240 for (Iterator<V> i = getModel().variables().iterator(); i.hasNext();) { 241 V aVariable = i.next(); 242 for (Iterator<T> j = aVariable.values(assignment).iterator(); j.hasNext();) { 243 T aValue = j.next(); 244 initNoGood(aValue, null); 245 goodValues(aVariable).add(aValue); 246 T current = assignment.getValue(aVariable); 247 if (revise(assignment, aValue)) { 248 queue.add(aValue); 249 } else if (current != null && !aValue.equals(current)) { 250 Set<T> noGood = new HashSet<T>(); 251 noGood.add(current); 252 setNoGood(aValue, noGood); 253 queue.add(aValue); 254 } 255 } 256 iProgress.incProgress(); 257 } 258 propagate(assignment, queue); 259 iProgress.restore(); 260 } 261 262 public Set<T>[] getNoGood(V variable) { 263 return iNoGood.get(variable); 264 } 265 266 public void setNoGood(V variable, Set<T>[] noGood) { 267 if (noGood == null) 268 iNoGood.remove(variable); 269 else 270 iNoGood.put(variable, noGood); 271 } 272 273 public Set<T> getNoGood(T value) { 274 Map<T, Set<T>> ng = iNoGoodVal.get(value.variable()); 275 if (ng == null) return null; 276 return ng.get(value); 277 } 278 279 public void setNoGood(T value, Set<T> noGood) { 280 Map<T, Set<T>> ng = iNoGoodVal.get(value.variable()); 281 if (ng == null) { 282 ng = new HashMap<T, Set<T>>(); 283 iNoGoodVal.put(value.variable(), ng); 284 } 285 if (noGood == null) 286 ng.remove(value); 287 else 288 ng.put(value, noGood); 289 } 290 291 /** support values of a variable */ 292 @SuppressWarnings("unchecked") 293 private Set<T> supportValues(V variable) { 294 Set<T>[] ret = getNoGood(variable); 295 if (ret == null) { 296 ret = new Set[] { new HashSet<T>(1000), new HashSet<T>() }; 297 setNoGood(variable, ret); 298 } 299 return ret[0]; 300 } 301 302 /** good values of a variable (values not removed from variables domain) 303 * @param variable given variable 304 * @return good values for the variable (i.e., values from the domain of the variable that have no no-good set) 305 **/ 306 @SuppressWarnings("unchecked") 307 public Set<T> goodValues(V variable) { 308 Set<T>[] ret = getNoGood(variable); 309 if (ret == null) { 310 ret = new Set[] { new HashSet<T>(1000), new HashSet<T>() }; 311 setNoGood(variable, ret); 312 } 313 return ret[1]; 314 } 315 316 /** notification that a no-good value becomes good or vice versa */ 317 private void goodnessChanged(T value) { 318 if (isGood(value)) { 319 goodValues(value.variable()).add(value); 320 } else { 321 goodValues(value.variable()).remove(value); 322 } 323 } 324 325 /** removes support of a variable */ 326 private void removeSupport(V variable, T value) { 327 supportValues(variable).remove(value); 328 } 329 330 /** adds support of a variable */ 331 private void addSupport(V variable, T value) { 332 supportValues(variable).add(value); 333 } 334 335 /** variables explanation 336 * @param value given value 337 * @return no-good set for the value 338 **/ 339 public Set<T> noGood(T value) { 340 return getNoGood(value); 341 } 342 343 /** is variable good 344 * @param value given value 345 * @return true if good, i.e., the value has no no-good set 346 **/ 347 public boolean isGood(T value) { 348 return (getNoGood(value) == null); 349 } 350 351 /** sets value to be good 352 * @param value given value 353 **/ 354 protected void setGood(T value) { 355 sLogger.debug(" -- set good " + value.variable().getName() + " = " + value.getName()); 356 Set<T> noGood = noGood(value); 357 if (noGood != null) 358 for (T v : noGood) 359 removeSupport(v.variable(), value); 360 setNoGood(value, null); 361 goodnessChanged(value); 362 } 363 364 /** sets values explanation (initialization) */ 365 private void initNoGood(T value, Set<T> reason) { 366 setNoGood(value, reason); 367 } 368 369 public void propagate(Assignment<V, T> assignment, List<T> queue) { 370 int idx = 0; 371 while (queue.size() > idx) { 372 T value = queue.get(idx++); 373 sLogger.debug(" -- propagate " + value.variable().getName() + " = " + value.getName() + " (noGood:" + noGood(value) + ")"); 374 if (goodValues(value.variable()).isEmpty()) { 375 sLogger.info("Empty domain detected for variable " + value.variable().getName()); 376 continue; 377 } 378 for (Constraint<V, T> constraint : value.variable().hardConstraints()) { 379 if (!contains(constraint)) 380 continue; 381 propagate(assignment, constraint, value, queue); 382 } 383 } 384 } 385 386 public void propagate(Assignment<V, T> assignment, Constraint<V, T> constraint, T noGoodValue, List<T> queue) { 387 for (V aVariable : constraint.variables()) { 388 if (aVariable.equals(noGoodValue.variable())) 389 continue; 390 for (Iterator<T> j = aVariable.values(assignment).iterator(); j.hasNext();) { 391 T aValue = j.next(); 392 if (isGood(aValue) && constraint.isConsistent(noGoodValue, aValue) 393 && !hasSupport(assignment, constraint, aValue, noGoodValue.variable())) { 394 setNoGood(aValue, explanation(assignment, constraint, aValue, noGoodValue.variable())); 395 queue.add(aValue); 396 } 397 } 398 } 399 } 400 401 public boolean revise(Assignment<V, T> assignment, T value) { 402 sLogger.debug(" -- revise " + value.variable().getName() + " = " + value.getName()); 403 for (Constraint<V, T> constraint : value.variable().hardConstraints()) { 404 if (!contains(constraint)) 405 continue; 406 if (revise(assignment, constraint, value)) 407 return true; 408 } 409 return false; 410 } 411 412 public boolean revise(Assignment<V, T> assignment, Constraint<V, T> constraint, T value) { 413 for (V aVariable : constraint.variables()) { 414 if (aVariable.equals(value.variable())) 415 continue; 416 if (!hasSupport(assignment, constraint, value, aVariable)) { 417 setNoGood(value, explanation(assignment, constraint, value, aVariable)); 418 return true; 419 } 420 } 421 return false; 422 } 423 424 public Set<T> explanation(Assignment<V, T> assignment, Constraint<V, T> constraint, T value, V variable) { 425 Set<T> expl = new HashSet<T>(); 426 for (T aValue : variable.values(assignment)) { 427 if (constraint.isConsistent(aValue, value)) { 428 expl.addAll(noGood(aValue)); 429 } 430 } 431 return expl; 432 } 433 434 public Set<T> supports(Assignment<V, T> assignment, Constraint<V, T> constraint, T value, V variable) { 435 Set<T> sup = new HashSet<T>(); 436 for (T aValue : variable.values(assignment)) { 437 if (!isGood(aValue)) 438 continue; 439 if (!constraint.isConsistent(aValue, value)) 440 continue; 441 sup.add(aValue); 442 } 443 return sup; 444 } 445 446 public boolean hasSupport(Assignment<V, T> assignment, Constraint<V, T> constraint, T value, V variable) { 447 for (T aValue : variable.values(assignment)) { 448 if (isGood(aValue) && constraint.isConsistent(aValue, value)) { 449 // sLogger.debug(" -- "+variable.getName()+" = "+aValue.getName()+" supports " 450 // + 451 // value.variable().getName()+" = "+value.getName()+" (constraint:"+constraint.getName()+")"); 452 return true; 453 } 454 } 455 // sLogger.debug(" -- value "+value.variable().getName()+" = " + 456 // value.getName()+" has no support from values of variable "+variable.getName()+" (constraint:"+constraint.getName()+")"); 457 /* 458 * for (Enumeration e=variable.values().elements();e.hasMoreElements();) 459 * { T aValue = (T)e.nextElement(); if 460 * (constraint.isConsistent(aValue,value)) { 461 * //sLogger.debug(" -- support " 462 * +aValue.getName()+" is not good: "+expl2str(noGood(aValue))); } } 463 */ 464 return false; 465 } 466 467 /** sets value's explanation 468 * @param assignment current assignment 469 * @param value a value 470 * @param reason no-good set for the value 471 **/ 472 public void setNoGood(Assignment<V, T> assignment, T value, Set<T> reason) { 473 sLogger.debug(" -- set nogood " + value.variable().getName() + " = " + value.getName() + "(expl:" + expl2str(reason) + ")"); 474 if (value.equals(assignment.getValue(value.variable()))) { 475 try { 476 throw new Exception("An assigned value " + value.variable().getName() + " = " + value.getName() + " become no good (noGood:" + reason + ")!!"); 477 } catch (Exception e) { 478 sLogger.warn(e.getMessage(), e); 479 } 480 checkExpl(assignment, reason); 481 printAssignments(assignment); 482 } 483 Set<T> noGood = noGood(value); 484 if (noGood != null) 485 for (T v : noGood) 486 removeSupport(v.variable(), value); 487 setNoGood(value, reason); 488 for (T aValue : reason) { 489 addSupport(aValue.variable(), value); 490 } 491 goodnessChanged(value); 492 } 493 } 494}