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 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 assignment current assignment 353 * @param value given value 354 **/ 355 protected void setGood(T value) { 356 sLogger.debug(" -- set good " + value.variable().getName() + " = " + value.getName()); 357 Set<T> noGood = noGood(value); 358 if (noGood != null) 359 for (T v : noGood) 360 removeSupport(v.variable(), value); 361 setNoGood(value, null); 362 goodnessChanged(value); 363 } 364 365 /** sets values explanation (initialization) */ 366 private void initNoGood(T value, Set<T> reason) { 367 setNoGood(value, reason); 368 } 369 370 public void propagate(Assignment<V, T> assignment, List<T> queue) { 371 int idx = 0; 372 while (queue.size() > idx) { 373 T value = queue.get(idx++); 374 sLogger.debug(" -- propagate " + value.variable().getName() + " = " + value.getName() + " (noGood:" + noGood(value) + ")"); 375 if (goodValues(value.variable()).isEmpty()) { 376 sLogger.info("Empty domain detected for variable " + value.variable().getName()); 377 continue; 378 } 379 for (Constraint<V, T> constraint : value.variable().hardConstraints()) { 380 if (!contains(constraint)) 381 continue; 382 propagate(assignment, constraint, value, queue); 383 } 384 } 385 } 386 387 public void propagate(Assignment<V, T> assignment, Constraint<V, T> constraint, T noGoodValue, List<T> queue) { 388 for (V aVariable : constraint.variables()) { 389 if (aVariable.equals(noGoodValue.variable())) 390 continue; 391 for (Iterator<T> j = aVariable.values(assignment).iterator(); j.hasNext();) { 392 T aValue = j.next(); 393 if (isGood(aValue) && constraint.isConsistent(noGoodValue, aValue) 394 && !hasSupport(assignment, constraint, aValue, noGoodValue.variable())) { 395 setNoGood(aValue, explanation(assignment, constraint, aValue, noGoodValue.variable())); 396 queue.add(aValue); 397 } 398 } 399 } 400 } 401 402 public boolean revise(Assignment<V, T> assignment, T value) { 403 sLogger.debug(" -- revise " + value.variable().getName() + " = " + value.getName()); 404 for (Constraint<V, T> constraint : value.variable().hardConstraints()) { 405 if (!contains(constraint)) 406 continue; 407 if (revise(assignment, constraint, value)) 408 return true; 409 } 410 return false; 411 } 412 413 public boolean revise(Assignment<V, T> assignment, Constraint<V, T> constraint, T value) { 414 for (V aVariable : constraint.variables()) { 415 if (aVariable.equals(value.variable())) 416 continue; 417 if (!hasSupport(assignment, constraint, value, aVariable)) { 418 setNoGood(value, explanation(assignment, constraint, value, aVariable)); 419 return true; 420 } 421 } 422 return false; 423 } 424 425 public Set<T> explanation(Assignment<V, T> assignment, Constraint<V, T> constraint, T value, V variable) { 426 Set<T> expl = new HashSet<T>(); 427 for (T aValue : variable.values(assignment)) { 428 if (constraint.isConsistent(aValue, value)) { 429 expl.addAll(noGood(aValue)); 430 } 431 } 432 return expl; 433 } 434 435 public Set<T> supports(Assignment<V, T> assignment, Constraint<V, T> constraint, T value, V variable) { 436 Set<T> sup = new HashSet<T>(); 437 for (T aValue : variable.values(assignment)) { 438 if (!isGood(aValue)) 439 continue; 440 if (!constraint.isConsistent(aValue, value)) 441 continue; 442 sup.add(aValue); 443 } 444 return sup; 445 } 446 447 public boolean hasSupport(Assignment<V, T> assignment, Constraint<V, T> constraint, T value, V variable) { 448 for (T aValue : variable.values(assignment)) { 449 if (isGood(aValue) && constraint.isConsistent(aValue, value)) { 450 // sLogger.debug(" -- "+variable.getName()+" = "+aValue.getName()+" supports " 451 // + 452 // value.variable().getName()+" = "+value.getName()+" (constraint:"+constraint.getName()+")"); 453 return true; 454 } 455 } 456 // sLogger.debug(" -- value "+value.variable().getName()+" = " + 457 // value.getName()+" has no support from values of variable "+variable.getName()+" (constraint:"+constraint.getName()+")"); 458 /* 459 * for (Enumeration e=variable.values().elements();e.hasMoreElements();) 460 * { T aValue = (T)e.nextElement(); if 461 * (constraint.isConsistent(aValue,value)) { 462 * //sLogger.debug(" -- support " 463 * +aValue.getName()+" is not good: "+expl2str(noGood(aValue))); } } 464 */ 465 return false; 466 } 467 468 /** sets value's explanation 469 * @param assignment current assignment 470 * @param value a value 471 * @param reason no-good set for the value 472 **/ 473 public void setNoGood(Assignment<V, T> assignment, T value, Set<T> reason) { 474 sLogger.debug(" -- set nogood " + value.variable().getName() + " = " + value.getName() + "(expl:" + expl2str(reason) + ")"); 475 if (value.equals(assignment.getValue(value.variable()))) { 476 try { 477 throw new Exception("An assigned value " + value.variable().getName() + " = " + value.getName() + " become no good (noGood:" + reason + ")!!"); 478 } catch (Exception e) { 479 sLogger.warn(e.getMessage(), e); 480 } 481 checkExpl(assignment, reason); 482 printAssignments(assignment); 483 } 484 Set<T> noGood = noGood(value); 485 if (noGood != null) 486 for (T v : noGood) 487 removeSupport(v.variable(), value); 488 setNoGood(value, reason); 489 for (T aValue : reason) { 490 addSupport(aValue.variable(), value); 491 } 492 goodnessChanged(value); 493 } 494 } 495}