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