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}