001package org.cpsolver.ifs.extension; 002 003import java.util.ArrayList; 004import java.util.Collection; 005import java.util.Comparator; 006import java.util.HashMap; 007import java.util.List; 008import java.util.Map; 009import java.util.Set; 010import java.util.TreeSet; 011import java.util.concurrent.locks.ReentrantReadWriteLock; 012 013import org.cpsolver.ifs.assignment.Assignment; 014import org.cpsolver.ifs.heuristics.ValueSelection; 015import org.cpsolver.ifs.heuristics.VariableSelection; 016import org.cpsolver.ifs.model.Constraint; 017import org.cpsolver.ifs.model.ConstraintListener; 018import org.cpsolver.ifs.model.Model; 019import org.cpsolver.ifs.model.Value; 020import org.cpsolver.ifs.model.Variable; 021import org.cpsolver.ifs.solution.Solution; 022import org.cpsolver.ifs.solver.Solver; 023import org.cpsolver.ifs.util.DataProperties; 024 025 026/** 027 * Conflict-based statistics. <br> 028 * <br> 029 * The idea behind it is to memorize conflicts and to avoid their potential 030 * repetition. When a value v0 is assigned to a variable V0, hard conflicts with 031 * previously assigned variables (e.g., V1 = v1, V2 = v2, ... Vm = vm) may 032 * occur. These variables V1,...,Vm have to be unassigned before the value v0 is 033 * assigned to the variable V0. These unassignments, together with the reason 034 * for their unassignment (i.e., the assignment V0 = v0), and a counter tracking 035 * how many times such an event occurred in the past, is stored in memory. <br> 036 * <br> 037 * Later, if a variable is selected for assignment again, the stored information 038 * about repetition of past hard conflicts can be taken into account, e.g., in 039 * the value selection heuristics. Assume that the variable V0 is selected for 040 * an assignment again (e.g., because it became unassigned as a result of a 041 * later assignment), we can weight the number of hard conflicts created in the 042 * past for each possible value of this variable. In the above example, the 043 * existing assignment V1 = v1 can prohibit the selection of value v0 for 044 * variable V0 if there is again a conflict with the assignment V1 = v1. <br> 045 * <br> 046 * Conflict-based statistics are a data structure which memorizes the number of 047 * hard conflicts that have occurred during the search (e.g., that assignment V0 048 * = v0 resulted c1 times in an unassignment of V1 = v1, c2 times of V2 = v2, . 049 * . . and cm times of Vm = vm). More precisely, they form an array 050 * <pre><code> 051 * CBS[Va = va, Vb != vb] = cab, 052 * </code></pre> 053 * stating that the assignment Va = va caused the unassignment of Vb = vb a 054 * total of cab times in the past. Note that in case of n-ary constraints (where 055 * n > 2), this does not imply that the assignments Va = va and Vb = vb cannot 056 * be used together. The proposed conflict-based statistics do not actually work 057 * with any constraint, they only memorize unassignments and the assignment that 058 * caused them. Let us consider a variable Va selected by the 059 * {@link VariableSelection#selectVariable(Solution)} function and a value va 060 * selected by {@link ValueSelection#selectValue(Solution, Variable)}. Once the 061 * assignment Vb = vb is selected by {@link Model#conflictValues(Assignment, Value)} to be 062 * unassigned, the array cell CBS[Va = va, Vb != vb] is incremented by one. <br> 063 * <br> 064 * The data structure is implemented as a hash table, storing information for 065 * conflict-based statistics. A counter is maintained for the tuple A = a and B 066 * != b. This counter is increased when the value a is assigned to the variable 067 * A and b is unassigned from B. The example of this structure 068 * <pre><code> 069 * A = a → 3 x B != b, 4 x B 070 * != c, 2 x C != a, 120 x D != a 071 * </code></pre> 072 * expresses that variable B lost its assignment b three times and its 073 * assignment c four times, variable C lost its assignment a two times, and D 074 * lost its assignment a 120 times, all because of later assignments of value a 075 * to variable A. This structure is being used in the value selection heuristics 076 * to evaluate existing conflicts with the assigned variables. For example, if 077 * there is a variable A selected and if the value a is in conflict with the 078 * assignment B = b, we know that a similar problem has already occurred 3x in 079 * the past, and hence the conflict A = a is weighted with the number 3. <br> 080 * <br> 081 * Then, a min-conflict value selection criterion, which selects a value with 082 * the minimal number of conflicts with the existing assignments, can be easily 083 * adapted to a weighted min-conflict criterion. The value with the smallest sum 084 * of the number of conflicts multiplied by their frequencies is selected. 085 * Stated in another way, the weighted min-conflict approach helps the value 086 * selection heuristics to select a value that might cause more conflicts than 087 * another value, but these conflicts occurred less frequently, and therefore 088 * they have a lower weighted sum. <br> 089 * <br> 090 * The conflict-based statistics has also implemented the following extensions: 091 * <ul> 092 * <li>If a variable is selected for an assignment, the above presented 093 * structure can also tell how many potential conflicts a value can cause in the 094 * future. In the above example, we already know that four times a later 095 * assignment of A=a caused that value c was unassigned from B. We can try to 096 * minimize such future conflicts by selecting a different value of the variable 097 * B while A is still unbound. 098 * <li>The memorized conflicts can be aged according to how far they have 099 * occurred in the past. For example, a conflict which occurred 1000 iterations 100 * ago can have half the weight of a conflict which occurred during the last 101 * iteration or it can be forgotten at all. 102 * </ul> 103 * Furthermore, the presented conflict-based statistics can be used not only 104 * inside the solving mechanism. The constructed "implications" together with 105 * the information about frequency of their occurrences can be easily accessed 106 * by users or by some add-on deductive engine to identify inconsistencies1 107 * and/or hard parts of the input problem. The user can then modify the input 108 * requirements in order to eliminate problems found and let the solver continue 109 * the search with this modified input problem. <br> 110 * <br> 111 * Parameters: <br> 112 * <table border='1'><caption>Related Solver Parameters</caption> 113 * <tr> 114 * <th>Parameter</th> 115 * <th>Type</th> 116 * <th>Comment</th> 117 * </tr> 118 * <tr> 119 * <td>ConflictStatistics.Ageing</td> 120 * <td>{@link Double}</td> 121 * <td>Ageing of the conflict-based statistics. Every memorized conflict is aged 122 * (multiplited) by this factor for every iteration which passed from the time 123 * it was memorized. For instance, if there was a conflict 10 iterations ago, 124 * its value is ageing^10 (default is 1.0 -- no ageing).</td> 125 * </tr> 126 * <tr> 127 * <td>ConflictStatistics.AgeingHalfTime</td> 128 * <td>{@link Integer}</td> 129 * <td>Another way how to express ageing: number of iterations to decrease a 130 * conflict to 1/2 (default is 0 -- no ageing)</td> 131 * </tr> 132 * </table> 133 * 134 * @see Solver 135 * @see Model 136 * @see ValueSelection 137 * @see VariableSelection 138 * 139 * @author Tomáš Müller 140 * @version IFS 1.3 (Iterative Forward Search)<br> 141 * Copyright (C) 2006 - 2014 Tomáš Müller<br> 142 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 143 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 144 * <br> 145 * This library is free software; you can redistribute it and/or modify 146 * it under the terms of the GNU Lesser General Public License as 147 * published by the Free Software Foundation; either version 3 of the 148 * License, or (at your option) any later version. <br> 149 * <br> 150 * This library is distributed in the hope that it will be useful, but 151 * WITHOUT ANY WARRANTY; without even the implied warranty of 152 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 153 * Lesser General Public License for more details. <br> 154 * <br> 155 * You should have received a copy of the GNU Lesser General Public 156 * License along with this library; if not see 157 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 158 * @param <V> Variable 159 * @param <T> Value 160 */ 161public class ConflictStatistics<V extends Variable<V, T>, T extends Value<V, T>> extends Extension<V, T> implements ConstraintListener<V, T> { 162 private static final String PARAM_AGEING = "ConflictStatistics.Ageing"; 163 private static final String PARAM_HALF_AGE = "ConflictStatistics.AgeingHalfTime"; 164 private static final String PARAM_PRINT = "ConflictStatistics.Print"; 165 166 private double iAgeing = 1.0; 167 private boolean iPrint = false; 168 169 private Map<AssignedValue<T>, List<AssignedValue<T>>> iAssignments = new HashMap<AssignedValue<T>, List<AssignedValue<T>>>(); 170 private Map<V, List<AssignedValue<T>>> iUnassignedVariables = new HashMap<V, List<AssignedValue<T>>>(); 171 private Map<AssignedValue<T>, List<AssignedValue<T>>> iNoGoods = new HashMap<AssignedValue<T>, List<AssignedValue<T>>>(); 172 173 private final ReentrantReadWriteLock iLock = new ReentrantReadWriteLock(); 174 175 public ConflictStatistics(Solver<V, T> solver, DataProperties properties) { 176 super(solver, properties); 177 iAgeing = properties.getPropertyDouble(PARAM_AGEING, iAgeing); 178 int halfAge = properties.getPropertyInt(PARAM_HALF_AGE, 0); 179 if (halfAge > 0) 180 iAgeing = Math.exp(Math.log(0.5) / (halfAge)); 181 iPrint = properties.getPropertyBoolean(PARAM_PRINT, iPrint); 182 } 183 184 @Override 185 public void register(Model<V, T> model) { 186 super.register(model); 187 } 188 189 @Override 190 public void unregister(Model<V, T> model) { 191 super.unregister(model); 192 } 193 194 private void variableUnassigned(long iteration, T unassignedValue, AssignedValue<T> noGood) { 195 if (iteration <= 0) return; 196 iLock.writeLock().lock(); 197 try { 198 AssignedValue<T> unass = new AssignedValue<T>(iteration, unassignedValue, iAgeing); 199 List<AssignedValue<T>> noGoodsForUnassignment = iNoGoods.get(unass); 200 if (noGoodsForUnassignment != null) { 201 if (noGoodsForUnassignment.contains(noGood)) { 202 (noGoodsForUnassignment.get(noGoodsForUnassignment.indexOf(noGood))).incCounter(iteration); 203 } else { 204 noGoodsForUnassignment.add(noGood); 205 } 206 } else { 207 noGoodsForUnassignment = new ArrayList<AssignedValue<T>>(); 208 noGoodsForUnassignment.add(noGood); 209 iNoGoods.put(unass, noGoodsForUnassignment); 210 } 211 } finally { 212 iLock.writeLock().unlock(); 213 } 214 } 215 216 public void reset() { 217 iLock.writeLock().lock(); 218 try { 219 iUnassignedVariables.clear(); 220 iAssignments.clear(); 221 } finally { 222 iLock.writeLock().unlock(); 223 } 224 } 225 226 public Map<AssignedValue<T>, List<AssignedValue<T>>> getNoGoods() { 227 return iNoGoods; 228 } 229 230 public void variableUnassigned(long iteration, T unassignedValue, T assignedValue) { 231 if (iteration <= 0) return; 232 AssignedValue<T> ass = new AssignedValue<T>(iteration, assignedValue, iAgeing); 233 AssignedValue<T> unass = new AssignedValue<T>(iteration, unassignedValue, iAgeing); 234 iLock.writeLock().lock(); 235 try { 236 if (iAssignments.containsKey(unass)) { 237 List<AssignedValue<T>> asss = iAssignments.get(unass); 238 if (asss.contains(ass)) { 239 asss.get(asss.indexOf(ass)).incCounter(iteration); 240 } else { 241 asss.add(ass); 242 } 243 } else { 244 List<AssignedValue<T>> asss = new ArrayList<AssignedValue<T>>(); 245 asss.add(ass); 246 iAssignments.put(unass, asss); 247 } 248 if (iUnassignedVariables.containsKey(unassignedValue.variable())) { 249 List<AssignedValue<T>> asss = iUnassignedVariables.get(unassignedValue.variable()); 250 if (asss.contains(ass)) { 251 (asss.get(asss.indexOf(ass))).incCounter(iteration); 252 } else { 253 asss.add(ass); 254 } 255 } else { 256 List<AssignedValue<T>> asss = new ArrayList<AssignedValue<T>>(); 257 asss.add(ass); 258 iUnassignedVariables.put(unassignedValue.variable(), asss); 259 } 260 } finally { 261 iLock.writeLock().unlock(); 262 } 263 } 264 265 /** 266 * Counts number of unassignments of the given conflicting values caused by 267 * the assignment of the given value. 268 * @param iteration current iteration 269 * @param conflictValues values conflicting with the given value 270 * @param value given value 271 * @return number of unassignments 272 */ 273 public double countRemovals(long iteration, Collection<T> conflictValues, T value) { 274 long ret = 0; 275 for (T conflictValue : conflictValues) { 276 ret += countRemovals(iteration, conflictValue, value); 277 // tady bylo +1 278 } 279 return ret; 280 } 281 282 /** 283 * Counts number of unassignments of the given conflicting value caused by 284 * the assignment of the given value. 285 * @param iteration current iteration 286 * @param conflictValue value conflicting with the given value 287 * @param value given value 288 * @return number of unassignments 289 */ 290 public double countRemovals(long iteration, T conflictValue, T value) { 291 iLock.readLock().lock(); 292 try { 293 List<AssignedValue<T>> asss = iUnassignedVariables.get(conflictValue.variable()); 294 if (asss == null) 295 return 0; 296 AssignedValue<T> ass = new AssignedValue<T>(iteration, value, iAgeing); 297 int idx = asss.indexOf(ass); 298 if (idx < 0) 299 return 0; 300 return (asss.get(idx)).getCounter(iteration); 301 } finally { 302 iLock.readLock().unlock(); 303 } 304 } 305 306 /** 307 * Counts potential number of unassignments of if the given value is 308 * selected. 309 * @param assignment current assignment 310 * @param iteration current iteration 311 * @param value given value 312 * @param limit conflict limit 313 * @return number of potential unassignments 314 */ 315 public long countPotentialConflicts(Assignment<V, T> assignment, long iteration, T value, int limit) { 316 iLock.readLock().lock(); 317 try { 318 List<AssignedValue<T>> asss = iAssignments.get(new AssignedValue<T>(iteration, value, iAgeing)); 319 if (asss == null) 320 return 0; 321 long count = 0; 322 for (AssignedValue<T> ass : asss) { 323 if (ass.getValue().variable().getAssignment(assignment) == null) { 324 if (limit >= 0) { 325 count += ass.getCounter(iteration) * Math.max(0, 1 + limit - value.variable().getModel().conflictValues(assignment, ass.getValue()).size()); 326 } else { 327 count += ass.getCounter(iteration); 328 } 329 } 330 } 331 return count; 332 } finally { 333 iLock.readLock().unlock(); 334 } 335 } 336 337 /** 338 * Count the number of past assignments of a variable 339 * @param variable given variable 340 * @return total number of past assignments 341 */ 342 public long countAssignments(V variable) { 343 iLock.readLock().lock(); 344 try { 345 List<AssignedValue<T>> assignments = iUnassignedVariables.get(variable); 346 if (assignments == null || assignments.isEmpty()) return 0; 347 double ret = 0; 348 for (AssignedValue<T> assignment: assignments) { 349 ret += assignment.getCounter(0); 350 } 351 return Math.round(ret); 352 } finally { 353 iLock.readLock().unlock(); 354 } 355 } 356 357 @Override 358 public String toString() { 359 iLock.readLock().lock(); 360 try { 361 if (iPrint) { 362 StringBuffer sb = new StringBuffer("Statistics{"); 363 TreeSet<AssignedValue<T>> sortedUnassignments = new TreeSet<AssignedValue<T>>(new Comparator<AssignedValue<T>>() { 364 @Override 365 public int compare(AssignedValue<T> x1, AssignedValue<T> x2) { 366 int c1 = 0, c2 = 0; 367 for (AssignedValue<T> y: iNoGoods.get(x1)) 368 c1 += y.getCounter(0); 369 for (AssignedValue<T> y: iNoGoods.get(x2)) 370 c2 += y.getCounter(0); 371 int cmp = Double.compare(c1, c2); 372 if (cmp != 0) 373 return -cmp; 374 return x1.compareTo(0, x2); 375 } 376 }); 377 sortedUnassignments.addAll(iNoGoods.keySet()); 378 int printedUnassignments = 0; 379 for (AssignedValue<T> x : sortedUnassignments) { 380 int c = 0; 381 for (AssignedValue<T> y: iNoGoods.get(x)) 382 c += y.getCounter(0); 383 sb.append("\n ").append(c + "x ").append(x.toString(0, false)).append(" <= {"); 384 TreeSet<AssignedValue<T>> sortedAssignments = new TreeSet<AssignedValue<T>>(new Comparator<AssignedValue<T>>() { 385 @Override 386 public int compare(AssignedValue<T> x1, AssignedValue<T> x2) { 387 int cmp = Double.compare(x1.getCounter(0), x2.getCounter(0)); 388 if (cmp != 0) 389 return -cmp; 390 return x1.compareTo(0, x2); 391 } 392 }); 393 sortedAssignments.addAll(iNoGoods.get(x)); 394 int printedAssignments = 0; 395 for (AssignedValue<T> y : sortedAssignments) { 396 sb.append("\n ").append(y.toString(0, true)); 397 if (++printedAssignments == 20) { 398 sb.append("\n ..."); 399 break; 400 } 401 } 402 sb.append("\n }"); 403 if (++printedUnassignments == 100) { 404 sb.append("\n ..."); 405 break; 406 } 407 } 408 sb.append("\n }"); 409 return sb.toString(); 410 } else { 411 StringBuffer sb = new StringBuffer("Statistics{"); 412 TreeSet<V> sortedUnassignedVariables = new TreeSet<V>(new Comparator<V>() { 413 @Override 414 public int compare(V v1, V v2) { 415 int cmp = Double.compare(countAssignments(v1), countAssignments(v2)); 416 if (cmp != 0) 417 return -cmp; 418 return v1.compareTo(v2); 419 } 420 }); 421 sortedUnassignedVariables.addAll(iUnassignedVariables.keySet()); 422 int printedVariables = 0; 423 for (V variable : sortedUnassignedVariables) { 424 sb.append("\n ").append(countAssignments(variable) + "x ").append(variable.getName()).append(" <= {"); 425 TreeSet<AssignedValue<T>> sortedAssignments = new TreeSet<AssignedValue<T>>(new Comparator<AssignedValue<T>>() { 426 @Override 427 public int compare(AssignedValue<T> x1, AssignedValue<T> x2) { 428 int cmp = Double.compare(x1.getCounter(0), x2.getCounter(0)); 429 if (cmp != 0) 430 return -cmp; 431 return x1.compareTo(0, x2); 432 } 433 }); 434 sortedAssignments.addAll(iUnassignedVariables.get(variable)); 435 int printedAssignments = 0; 436 for (AssignedValue<T> x : sortedAssignments) { 437 sb.append("\n ").append(x.toString(0, true)); 438 if (++printedAssignments == 20) { 439 sb.append("\n ..."); 440 break; 441 } 442 } 443 sb.append("\n }"); 444 if (++printedVariables == 100) { 445 sb.append("\n ..."); 446 break; 447 } 448 } 449 sb.append("\n }"); 450 return sb.toString(); 451 } 452 } finally { 453 iLock.readLock().unlock(); 454 } 455 } 456 457 @Override 458 public void constraintBeforeAssigned(Assignment<V, T> assignment, long iteration, Constraint<V, T> constraint, T assigned, Set<T> unassigned) { 459 } 460 461 /** Increments appropriate counters when there is a value unassigned */ 462 @Override 463 public void constraintAfterAssigned(Assignment<V, T> assignment, long iteration, Constraint<V, T> constraint, T assigned, Set<T> unassigned) { 464 if (iteration <= 0) 465 return; 466 if (unassigned == null || unassigned.isEmpty()) 467 return; 468 if (iPrint) { 469 // AssignmentSet noGoods = 470 // AssignmentSet.createAssignmentSet(iteration,unassigned, iAgeing); 471 // noGoods.addAssignment(iteration, assigned, iAgeing); 472 // noGoods.setConstraint(constraint); 473 AssignedValue<T> noGood = new AssignedValue<T>(iteration, assigned, iAgeing); 474 noGood.setConstraint(constraint); 475 for (T unassignedValue : unassigned) { 476 variableUnassigned(iteration, unassignedValue, noGood); 477 variableUnassigned(iteration, unassignedValue, assigned); 478 } 479 } else { 480 for (T unassignedValue : unassigned) { 481 variableUnassigned(iteration, unassignedValue, assigned); 482 } 483 } 484 } 485 486 @Override 487 public void constraintAdded(Constraint<V, T> constraint) { 488 constraint.addConstraintListener(this); 489 } 490 491 @Override 492 public void constraintRemoved(Constraint<V, T> constraint) { 493 constraint.removeConstraintListener(this); 494 } 495}