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 &nbsp;&nbsp;&nbsp; &#8594; &nbsp;&nbsp;&nbsp; 3 x B != b, &nbsp; 4 x B
067     * != c, &nbsp; 2 x C != a, &nbsp; 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    }