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}