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