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