    001package org.cpsolver.ifs.dbt;
    002
    003import java.util.ArrayList;
    004import java.util.Collection;
    005import java.util.HashSet;
    006import java.util.Set;
    007
    008import org.cpsolver.ifs.assignment.Assignment;
    009import org.cpsolver.ifs.extension.Extension;
    010import org.cpsolver.ifs.extension.ViolatedInitials;
    011import org.cpsolver.ifs.heuristics.GeneralValueSelection;
    012import org.cpsolver.ifs.heuristics.ValueSelection;
    013import org.cpsolver.ifs.model.Value;
    014import org.cpsolver.ifs.model.Variable;
    015import org.cpsolver.ifs.solution.Solution;
    016import org.cpsolver.ifs.solver.Solver;
    017import org.cpsolver.ifs.util.DataProperties;
    018import org.cpsolver.ifs.util.ToolBox;
    019
    020
    021/**
    022 * Selection of a value for dynamic backtracking. <br>
    023 * <br>
    024 * <ul>
    025 * <li>Returns null if all values of the selected variable are nogood.
    026 * <li>Selected the best good value (according to the parameters) of the selected variable.
    027 * </ul>
    028 * <br>
    029 * It is based on a weighted sum of several criteria. <br>
    030 * <br>
    031 * This IFS solver value selection heuristics is to be used only in case of
    032 * dynamic backtracking and it has the following parameters: <br>
    033 * <table border='1'><caption>Related Solver Parameters</caption>
    034 * <tr>
    035 * <th>Parameter</th>
    036 * <th>Type</th>
    037 * <th>Comment</th>
    038 * </tr>
    039 * <tr>
    040 * <td>General.MPP</td>
    041 * <td>{@link Boolean}</td>
    042 * <td>Minimal Perturbation Problem</td>
    043 * </tr>
    044 * <tr>
    045 * <td>Value.MPPLimit</td>
    046 * <td>{@link Integer}</td>
    047 * <td>Limit on the number of perturbations (only in case of MPP, i.e., when
    048 * General.MPP=true). MPP limit is decreased when a complete solution is found.
    049 * If set to -1, it is no used</td>
    050 * </tr>
    051 * <tr>
    052 * <td>Value.InitialSelectionProb</td>
    053 * <td>{@link Double}</td>
    054 * <td>Probability of selection of initial value (only in case of MPP)</td>
    055 * </tr>
    056 * <tr>
    057 * <td>Value.WeightDeltaInitialAssignments</td>
    058 * <td>{@link Double}</td>
    059 * <td>Weight of difference in the number of assignments of initial values in
    060 * case of selection of the value(only in case of MPP)</td>
    061 * </tr>
    062 * <tr>
    063 * <td>Value.RandomWalkProb</td>
    064 * <td>{@link Double}</td>
    065 * <td>Probability of random selection of a good value</td>
    066 * </tr>
    067 * <tr>
    068 * <td>Value.WeightNrAssignments</td>
    069 * <td>{@link Double}</td>
    070 * <td>Weight of the number of previous assignments of the value</td>
    071 * </tr>
    072 * <tr>
    073 * <td>Value.WeightValue</td>
    074 * <td>{@link Double}</td>
    075 * <td>Weight of the value itself (e.g., for minCSP)</td>
    076 * </tr>
    077 * </table>
    078 * <br>
    079 *
    080 * @author  Tomáš Müller
    081 * @version IFS 1.3 (Iterative Forward Search)<br>
    082 *          Copyright (C) 2006 - 2014 Tomáš Müller<br>
    083 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    084 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    085 * <br>
    086 *          This library is free software; you can redistribute it and/or modify
    087 *          it under the terms of the GNU Lesser General Public License as
    088 *          published by the Free Software Foundation; either version 3 of the
    089 *          License, or (at your option) any later version. <br>
    090 * <br>
    091 *          This library is distributed in the hope that it will be useful, but
    092 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    093 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    094 *          Lesser General Public License for more details. <br>
    095 * <br>
    096 *          You should have received a copy of the GNU Lesser General Public
    097 *          License along with this library; if not see
    098 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    099 * @param <V> Variable
    100 * @param <T> Value
    101 */
    102public class DbtValueSelection<V extends Variable<V, T>, T extends Value<V, T>> implements ValueSelection<V, T> {
    103    private static org.apache.logging.log4j.Logger sLogger = org.apache.logging.log4j.LogManager.getLogger(GeneralValueSelection.class);
    104    private double iRandomWalkProb = 0.0;
    105    private double iInitialSelectionProb = 0.0;
    106    private int iMPPLimit = -1;
    107
    108    private double iWeightDeltaInitialAssignment = 0.0;
    109    private double iWeightValue = 0.0;
    110
    111    private boolean iMPP = false;
    112    private DbtPropagation<V, T> iProp = null;
    113    private ViolatedInitials<V, T> iViolatedInitials = null;
    114
    115    public DbtValueSelection(DataProperties properties) {
    116        iMPP = properties.getPropertyBoolean("General.MPP", false);
    117
    118        if (iMPP) {
    119            iMPPLimit = properties.getPropertyInt("Value.MPPLimit", -1);
    120            iInitialSelectionProb = properties.getPropertyDouble("Value.InitialSelectionProb", 0.75);
    121            iWeightDeltaInitialAssignment = properties.getPropertyDouble("Value.WeightDeltaInitialAssignments", 0.0);
    122        }
    123
    124        iRandomWalkProb = properties.getPropertyDouble("Value.RandomWalkProb", 0.0);
    125        iWeightValue = properties.getPropertyDouble("Value.WeightValue", 0.0);
    126    }
    127
    128    /**
    129     * Heuristics initialization
    130     *
    131     * @see ValueSelection#init(Solver)
    132     */
    133    @Override
    134    public void init(Solver<V, T> solver) {
    135        for (Extension<V, T> extension : solver.getExtensions()) {
    136            if (DbtPropagation.class.isInstance(extension)) {
    137                iProp = (DbtPropagation<V, T>) extension;
    138            }
    139            if (ViolatedInitials.class.isInstance(extension)) {
    140                iViolatedInitials = (ViolatedInitials<V, T>) extension;
    141            }
    142        }
    143    }
    144
    145    /**
    146     * Value selection
    147     *
    148     * @see ValueSelection#selectValue(Solution, Variable)
    149     */
    150    @Override
    151    public T selectValue(Solution<V, T> solution, V selectedVariable) {
    152        ArrayList<T> values = null;
    153        Assignment<V, T> assignment = solution.getAssignment();
    154
    155        if (iProp != null) {
    156            values = new ArrayList<T>(iProp.goodValues(assignment, selectedVariable).size());
    157            for (T value : selectedVariable.values(solution.getAssignment())) {
    158                if (!iProp.isGood(assignment, value)) {
    159                    continue;
    160                }
    161                Collection<T> conf = solution.getModel().conflictValues(assignment, value);
    162
    163                if (!conf.isEmpty()) {
    164                    Set<T> noGood = new HashSet<T>(2 * conf.size());
    165
    166                    for (T v : conf) {
    167                        noGood.add(v);
    168                    }
    169                    iProp.setNoGood(assignment, value, noGood);
    170                    sLogger.debug(value + " become nogood (" + noGood + ")");
    171                } else {
    172                    if (!solution.isBestComplete() || solution.getModel().getBestValue() > solution.getModel().getTotalValue(assignment) + value.toDouble(assignment)) {
    173                        values.add(value);
    174                    }
    175                }
    176            }
    177        } else {
    178            values = new ArrayList<T>(selectedVariable.values(solution.getAssignment()).size());
    179            for (T value : selectedVariable.values(solution.getAssignment())) {
    180                if (solution.getModel().conflictValues(assignment, value).isEmpty()) {
    181                    if (solution.isBestComplete() && solution.getModel().getBestValue() > solution.getModel().getTotalValue(assignment) + value.toDouble(assignment)) {
    182                        values.add(value);
    183                    }
    184                }
    185            }
    186        }
    187        if (values.isEmpty()) {
    188            return null;
    189        }
    190
    191        if (iMPP) {
    192            if (iMPPLimit >= 0 && solution.isBestComplete() && solution.getModel().getBestPerturbations() >= 0
    193                    && solution.getModel().getBestPerturbations() <= iMPPLimit) {
    194                iMPPLimit = solution.getModel().getBestPerturbations() - 1;
    195                sLogger.debug("MPP Limit decreased to " + iMPPLimit);
    196            }
    197
    198            int nrPerts = solution.getModel().perturbVariables(assignment).size();
    199
    200            if (iMPPLimit >= 0 && iMPPLimit < nrPerts) {
    201                return null;
    202            }
    203            if (iMPPLimit >= 0 && iMPPLimit == nrPerts && selectedVariable.getInitialAssignment() != null) {
    204                if (values.contains(selectedVariable.getInitialAssignment())) {
    205                    return selectedVariable.getInitialAssignment();
    206                }
    207                return null;
    208            }
    209
    210            if (selectedVariable.getInitialAssignment() != null && ToolBox.random() <= iInitialSelectionProb) {
    211                if (values.contains(selectedVariable.getInitialAssignment())) {
    212                    return selectedVariable.getInitialAssignment();
    213                }
    214            }
    215        }
    216
    217        if (values.size() == 1) {
    218            return values.get(0);
    219        }
    220
    221        if (ToolBox.random() <= iRandomWalkProb) {
    222            return ToolBox.random(values);
    223        }
    224
    225        ArrayList<T> bestValues = null;
    226        double bestWeightedSum = 0;
    227
    228        if (iWeightDeltaInitialAssignment == 0.0 && iWeightValue == 0.0) {
    229            return ToolBox.random(values);
    230        }
    231
    232        for (T value : values) {
    233
    234            long deltaInitialAssignments = 0;
    235
    236            if (iWeightDeltaInitialAssignment != 0.0) {
    237                if (iViolatedInitials != null) {
    238                    Set<T> violations = iViolatedInitials.getViolatedInitials(value);
    239
    240                    if (violations != null) {
    241                        for (T aValue : violations) {
    242                            if (assignment.getValue(aValue.variable()) == null || assignment.getValue(aValue.variable()).equals(aValue)) {
    243                                deltaInitialAssignments += 2;
    244                            }
    245                        }
    246                    }
    247                }
    248                if (selectedVariable.getInitialAssignment() != null
    249                        && !selectedVariable.getInitialAssignment().equals(value)) {
    250                    deltaInitialAssignments++;
    251                }
    252                if (iMPPLimit >= 0 && (solution.getModel().perturbVariables(assignment).size() + deltaInitialAssignments) > iMPPLimit) {
    253                    continue;
    254                }
    255            }
    256
    257            double weightedSum = (iWeightDeltaInitialAssignment * deltaInitialAssignments) + (iWeightValue * value.toDouble(assignment));
    258
    259            if (bestValues == null || bestWeightedSum > weightedSum) {
    260                bestWeightedSum = weightedSum;
    261                if (bestValues == null) {
    262                    bestValues = new ArrayList<T>();
    263                } else {
    264                    bestValues.clear();
    265                }
    266                bestValues.add(value);
    267            } else if (bestWeightedSum == weightedSum) {
    268                bestValues.add(value);
    269            }
    270        }
    271        return (bestValues == null ? null : (T) ToolBox.random(bestValues));
    272    }
    273}