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}