    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 &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 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}