001 package net.sf.cpsolver.ifs.extension;
002
003 import java.util.ArrayList;
004 import java.util.Collection;
005 import java.util.Comparator;
006 import java.util.HashMap;
007 import java.util.List;
008 import java.util.Map;
009 import java.util.Set;
010 import java.util.TreeSet;
011
012 import net.sf.cpsolver.ifs.heuristics.ValueSelection;
013 import net.sf.cpsolver.ifs.heuristics.VariableSelection;
014 import net.sf.cpsolver.ifs.model.Constraint;
015 import net.sf.cpsolver.ifs.model.ConstraintListener;
016 import net.sf.cpsolver.ifs.model.Model;
017 import net.sf.cpsolver.ifs.model.Value;
018 import net.sf.cpsolver.ifs.model.Variable;
019 import net.sf.cpsolver.ifs.solution.Solution;
020 import net.sf.cpsolver.ifs.solver.Solver;
021 import 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 Tomas Muller<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 */
155 public 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 }