001 package net.sf.cpsolver.ifs.dbt;
002
003 import java.util.ArrayList;
004 import java.util.Collection;
005 import java.util.HashSet;
006 import java.util.Set;
007
008 import net.sf.cpsolver.ifs.extension.Extension;
009 import net.sf.cpsolver.ifs.extension.ViolatedInitials;
010 import net.sf.cpsolver.ifs.heuristics.GeneralValueSelection;
011 import net.sf.cpsolver.ifs.heuristics.ValueSelection;
012 import net.sf.cpsolver.ifs.model.Value;
013 import net.sf.cpsolver.ifs.model.Variable;
014 import net.sf.cpsolver.ifs.solution.Solution;
015 import net.sf.cpsolver.ifs.solver.Solver;
016 import net.sf.cpsolver.ifs.util.DataProperties;
017 import 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 Tomas Muller<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 */
096 public 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 }