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}