    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' summary='Related Solver Parameters'>
    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 * @version IFS 1.3 (Iterative Forward Search)<br>
    081 *          Copyright (C) 2006 - 2014 Tomáš Müller<br>
    082 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    083 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    084 * <br>
    085 *          This library is free software; you can redistribute it and/or modify
    086 *          it under the terms of the GNU Lesser General Public License as
    087 *          published by the Free Software Foundation; either version 3 of the
    088 *          License, or (at your option) any later version. <br>
    089 * <br>
    090 *          This library is distributed in the hope that it will be useful, but
    091 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    092 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    093 *          Lesser General Public License for more details. <br>
    094 * <br>
    095 *          You should have received a copy of the GNU Lesser General Public
    096 *          License along with this library; if not see
    097 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    098 * @param <V> Variable
    099 * @param <T> Value
    100 */
    101public class DbtValueSelection<V extends Variable<V, T>, T extends Value<V, T>> implements ValueSelection<V, T> {
    102    private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(GeneralValueSelection.class);
    103    private double iRandomWalkProb = 0.0;
    104    private double iInitialSelectionProb = 0.0;
    105    private int iMPPLimit = -1;
    106
    107    private double iWeightDeltaInitialAssignment = 0.0;
    108    private double iWeightValue = 0.0;
    109
    110    private boolean iMPP = false;
    111    private DbtPropagation<V, T> iProp = null;
    112    private ViolatedInitials<V, T> iViolatedInitials = null;
    113
    114    public DbtValueSelection(DataProperties properties) {
    115        iMPP = properties.getPropertyBoolean("General.MPP", false);
    116
    117        if (iMPP) {
    118            iMPPLimit = properties.getPropertyInt("Value.MPPLimit", -1);
    119            iInitialSelectionProb = properties.getPropertyDouble("Value.InitialSelectionProb", 0.75);
    120            iWeightDeltaInitialAssignment = properties.getPropertyDouble("Value.WeightDeltaInitialAssignments", 0.0);
    121        }
    122
    123        iRandomWalkProb = properties.getPropertyDouble("Value.RandomWalkProb", 0.0);
    124        iWeightValue = properties.getPropertyDouble("Value.WeightValue", 0.0);
    125    }
    126
    127    /**
    128     * Heuristics initialization
    129     *
    130     * @see ValueSelection#init(Solver)
    131     */
    132    @Override
    133    public void init(Solver<V, T> solver) {
    134        for (Extension<V, T> extension : solver.getExtensions()) {
    135            if (DbtPropagation.class.isInstance(extension)) {
    136                iProp = (DbtPropagation<V, T>) extension;
    137            }
    138            if (ViolatedInitials.class.isInstance(extension)) {
    139                iViolatedInitials = (ViolatedInitials<V, T>) extension;
    140            }
    141        }
    142    }
    143
    144    /**
    145     * Value selection
    146     *
    147     * @see ValueSelection#selectValue(Solution, Variable)
    148     */
    149    @Override
    150    public T selectValue(Solution<V, T> solution, V selectedVariable) {
    151        ArrayList<T> values = null;
    152        Assignment<V, T> assignment = solution.getAssignment();
    153
    154        if (iProp != null) {
    155            values = new ArrayList<T>(iProp.goodValues(assignment, selectedVariable).size());
    156            for (T value : selectedVariable.values(solution.getAssignment())) {
    157                if (!iProp.isGood(assignment, value)) {
    158                    continue;
    159                }
    160                Collection<T> conf = solution.getModel().conflictValues(assignment, value);
    161
    162                if (!conf.isEmpty()) {
    163                    Set<T> noGood = new HashSet<T>(2 * conf.size());
    164
    165                    for (T v : conf) {
    166                        noGood.add(v);
    167                    }
    168                    iProp.setNoGood(assignment, value, noGood);
    169                    sLogger.debug(value + " become nogood (" + noGood + ")");
    170                } else {
    171                    if (!solution.isBestComplete() || solution.getModel().getBestValue() > solution.getModel().getTotalValue(assignment) + value.toDouble(assignment)) {
    172                        values.add(value);
    173                    }
    174                }
    175            }
    176        } else {
    177            values = new ArrayList<T>(selectedVariable.values(solution.getAssignment()).size());
    178            for (T value : selectedVariable.values(solution.getAssignment())) {
    179                if (solution.getModel().conflictValues(assignment, value).isEmpty()) {
    180                    if (solution.isBestComplete() && solution.getModel().getBestValue() > solution.getModel().getTotalValue(assignment) + value.toDouble(assignment)) {
    181                        values.add(value);
    182                    }
    183                }
    184            }
    185        }
    186        if (values.isEmpty()) {
    187            return null;
    188        }
    189
    190        if (iMPP) {
    191            if (iMPPLimit >= 0 && solution.isBestComplete() && solution.getModel().getBestPerturbations() >= 0
    192                    && solution.getModel().getBestPerturbations() <= iMPPLimit) {
    193                iMPPLimit = solution.getModel().getBestPerturbations() - 1;
    194                sLogger.debug("MPP Limit decreased to " + iMPPLimit);
    195            }
    196
    197            int nrPerts = solution.getModel().perturbVariables(assignment).size();
    198
    199            if (iMPPLimit >= 0 && iMPPLimit < nrPerts) {
    200                return null;
    201            }
    202            if (iMPPLimit >= 0 && iMPPLimit == nrPerts && selectedVariable.getInitialAssignment() != null) {
    203                if (values.contains(selectedVariable.getInitialAssignment())) {
    204                    return selectedVariable.getInitialAssignment();
    205                }
    206                return null;
    207            }
    208
    209            if (selectedVariable.getInitialAssignment() != null && ToolBox.random() <= iInitialSelectionProb) {
    210                if (values.contains(selectedVariable.getInitialAssignment())) {
    211                    return selectedVariable.getInitialAssignment();
    212                }
    213            }
    214        }
    215
    216        if (values.size() == 1) {
    217            return values.get(0);
    218        }
    219
    220        if (ToolBox.random() <= iRandomWalkProb) {
    221            return ToolBox.random(values);
    222        }
    223
    224        ArrayList<T> bestValues = null;
    225        double bestWeightedSum = 0;
    226
    227        if (iWeightDeltaInitialAssignment == 0.0 && iWeightValue == 0.0) {
    228            return ToolBox.random(values);
    229        }
    230
    231        for (T value : values) {
    232
    233            long deltaInitialAssignments = 0;
    234
    235            if (iWeightDeltaInitialAssignment != 0.0) {
    236                if (iViolatedInitials != null) {
    237                    Set<T> violations = iViolatedInitials.getViolatedInitials(value);
    238
    239                    if (violations != null) {
    240                        for (T aValue : violations) {
    241                            if (assignment.getValue(aValue.variable()) == null || assignment.getValue(aValue.variable()).equals(aValue)) {
    242                                deltaInitialAssignments += 2;
    243                            }
    244                        }
    245                    }
    246                }
    247                if (selectedVariable.getInitialAssignment() != null
    248                        && !selectedVariable.getInitialAssignment().equals(value)) {
    249                    deltaInitialAssignments++;
    250                }
    251                if (iMPPLimit >= 0 && (solution.getModel().perturbVariables(assignment).size() + deltaInitialAssignments) > iMPPLimit) {
    252                    continue;
    253                }
    254            }
    255
    256            double weightedSum = (iWeightDeltaInitialAssignment * deltaInitialAssignments) + (iWeightValue * value.toDouble(assignment));
    257
    258            if (bestValues == null || bestWeightedSum > weightedSum) {
    259                bestWeightedSum = weightedSum;
    260                if (bestValues == null) {
    261                    bestValues = new ArrayList<T>();
    262                } else {
    263                    bestValues.clear();
    264                }
    265                bestValues.add(value);
    266            } else if (bestWeightedSum == weightedSum) {
    267                bestValues.add(value);
    268            }
    269        }
    270        return (bestValues == null ? null : (T) ToolBox.random(bestValues));
    271    }
    272}