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