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}