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