001package org.cpsolver.ifs.heuristics; 002 003import java.util.ArrayList; 004import java.util.Collection; 005import java.util.Iterator; 006import java.util.List; 007import java.util.Set; 008 009import org.cpsolver.ifs.assignment.Assignment; 010import org.cpsolver.ifs.extension.ConflictStatistics; 011import org.cpsolver.ifs.extension.Extension; 012import org.cpsolver.ifs.extension.MacPropagation; 013import org.cpsolver.ifs.extension.ViolatedInitials; 014import org.cpsolver.ifs.model.Model; 015import org.cpsolver.ifs.model.Value; 016import org.cpsolver.ifs.model.Variable; 017import org.cpsolver.ifs.solution.Solution; 018import org.cpsolver.ifs.solver.Solver; 019import org.cpsolver.ifs.util.DataProperties; 020import org.cpsolver.ifs.util.ToolBox; 021 022 023/** 024 * General implementation of value selection criterion. <br> 025 * <br> 026 * Value selection criterion is based on weighted sum of various criteria. It 027 * also allows random walk technique and tabu search. <br> 028 * Parameters: <br> 029 * <table border='1' summary='Related Solver Parameters'> 030 * <tr> 031 * <th>Parameter</th> 032 * <th>Type</th> 033 * <th>Comment</th> 034 * </tr> 035 * <tr> 036 * <td>General.MPP</td> 037 * <td>{@link Boolean}</td> 038 * <td>if true, MPP is being solved</td> 039 * </tr> 040 * <tr> 041 * <td>Value.MPPLimit</td> 042 * <td>{@link Integer}</td> 043 * <td>MPP: limitation of the number of allowed perturbations. If a solution 044 * within this limit is gound, it is decreased.</td> 045 * </tr> 046 * <tr> 047 * <td>Value.InitialSelectionProb</td> 048 * <td>{@link Double}</td> 049 * <td>MPP: probability of selection of the initial value</td> 050 * </tr> 051 * <tr> 052 * <td>Value.RandomWalkProb</td> 053 * <td>{@link Double}</td> 054 * <td>Random Walk: probability of selection of a value randomly among all the 055 * values</td> 056 * </tr> 057 * <tr> 058 * <td>Value.Tabu</td> 059 * <td>{@link Integer}</td> 060 * <td>Tabu Search: length of the tabu-list</td> 061 * </tr> 062 * <tr> 063 * <td>Value.GoodSelectionProb</td> 064 * <td>{@link Double}</td> 065 * <td>In case of {@link MacPropagation}, with this probability (1.0 means 066 * always), the selection is made only among good values (not removed from the 067 * domain).</td> 068 * </tr> 069 * </table> 070 * <br> 071 * Following weights are used in the weighted sum (computed for all values). The 072 * value with the lowest weighted sum is selected. If there are more than one of 073 * such values, one of them is selected randomly. <br> 074 * <table border='1' summary='Related Solver Parameters'> 075 * <tr> 076 * <th>Parameter</th> 077 * <th>Type</th> 078 * <th>Comment</th> 079 * </tr> 080 * <tr> 081 * <td>Value.WeightDeltaInitialAssignments</td> 082 * <td>{@link Double}</td> 083 * <td>MPP: Difference in the number of assigned initial values if the value is 084 * assigned to the variable (weighted by this 085 * Value.WeightDeltaInitialAssignments): -1 if the value is initial, 0 086 * otherwise, increased by the number of initial values assigned to variables 087 * with hard conflicts with the value</td> 088 * </tr> 089 * <tr> 090 * <td>Value.WeightWeightedConflicts</td> 091 * <td>{@link Double}</td> 092 * <td>When {@link ConflictStatistics} is used: weighted number of conflicting 093 * variables</td> 094 * </tr> 095 * <tr> 096 * <td>Value.WeightPotentialConflicts</td> 097 * <td>{@link Double}</td> 098 * <td>When {@link ConflictStatistics} is used: weighted number of potentially 099 * conflicting variables</td> 100 * </tr> 101 * <tr> 102 * <td>Value.WeightConflicts</td> 103 * <td>{@link Double}</td> 104 * <td>Number of conflicting variables {@link Model#conflictValues(Assignment, Value)}.</td> 105 * </tr> 106 * <tr> 107 * <td>Value.WeightValue</td> 108 * <td>{@link Double}</td> 109 * <td>Value {@link Value#toDouble(Assignment)}</td> 110 * </tr> 111 * </table> 112 * 113 * @see VariableSelection 114 * @see Solver 115 * 116 * @version IFS 1.3 (Iterative Forward Search)<br> 117 * Copyright (C) 2006 - 2014 Tomáš Müller<br> 118 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 119 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 120 * <br> 121 * This library is free software; you can redistribute it and/or modify 122 * it under the terms of the GNU Lesser General Public License as 123 * published by the Free Software Foundation; either version 3 of the 124 * License, or (at your option) any later version. <br> 125 * <br> 126 * This library is distributed in the hope that it will be useful, but 127 * WITHOUT ANY WARRANTY; without even the implied warranty of 128 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 129 * Lesser General Public License for more details. <br> 130 * <br> 131 * You should have received a copy of the GNU Lesser General Public 132 * License along with this library; if not see <a href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>. 133 * 134 * @param <V> Variable 135 * @param <T> Value 136 **/ 137public class GeneralValueSelection<V extends Variable<V, T>, T extends Value<V, T>> implements ValueSelection<V, T> { 138 private double iRandomWalkProb = 0.0; 139 private double iInitialSelectionProb = 0.0; 140 private double iGoodSelectionProb = 0.0; 141 private int iMPPLimit = -1; 142 143 private double iWeightDeltaInitialAssignment = 0.0; 144 private double iWeightPotentialConflicts = 0.0; 145 private double iWeightWeightedCoflicts = 0.0; 146 private double iWeightCoflicts = 1.0; 147 private double iWeightValue = 0.0; 148 149 protected int iTabuSize = 0; 150 protected ArrayList<T> iTabu = null; 151 protected int iTabuPos = 0; 152 153 private boolean iMPP = false; 154 private ConflictStatistics<V, T> iStat = null; 155 private MacPropagation<V, T> iProp = null; 156 private ViolatedInitials<V, T> iViolatedInitials = null; 157 158 public GeneralValueSelection() { 159 } 160 161 /** 162 * Constructor 163 * 164 * @param properties 165 * input configuration 166 */ 167 public GeneralValueSelection(DataProperties properties) { 168 iMPP = properties.getPropertyBoolean("General.MPP", false); 169 if (iMPP) { 170 iMPPLimit = properties.getPropertyInt("Value.MPPLimit", -1); 171 iInitialSelectionProb = properties.getPropertyDouble("Value.InitialSelectionProb", 0.75); 172 iWeightDeltaInitialAssignment = properties.getPropertyDouble("Value.WeightDeltaInitialAssignments", 0.0); 173 } 174 iGoodSelectionProb = properties.getPropertyDouble("Value.GoodSelectionProb", 0.00); 175 iWeightWeightedCoflicts = properties.getPropertyDouble("Value.WeightWeightedConflicts", 1.0); 176 iWeightPotentialConflicts = properties.getPropertyDouble("Value.WeightPotentialConflicts", 0.0); 177 178 iRandomWalkProb = properties.getPropertyDouble("Value.RandomWalkProb", 0.0); 179 iWeightCoflicts = properties.getPropertyDouble("Value.WeightConflicts", 1.0); 180 iWeightValue = properties.getPropertyDouble("Value.WeightValue", 0.0); 181 iTabuSize = properties.getPropertyInt("Value.Tabu", 0); 182 if (iTabuSize > 0) 183 iTabu = new ArrayList<T>(iTabuSize); 184 } 185 186 /** Initialization */ 187 @Override 188 public void init(Solver<V, T> solver) { 189 for (Extension<V, T> extension : solver.getExtensions()) { 190 if (ConflictStatistics.class.isInstance(extension)) 191 iStat = (ConflictStatistics<V, T>) extension; 192 if (MacPropagation.class.isInstance(extension)) 193 iProp = (MacPropagation<V, T>) extension; 194 if (ViolatedInitials.class.isInstance(extension)) 195 iViolatedInitials = (ViolatedInitials<V, T>) extension; 196 } 197 } 198 199 /** Value selection */ 200 @Override 201 public T selectValue(Solution<V, T> solution, V selectedVariable) { 202 if (iMPP) { 203 if (selectedVariable.getInitialAssignment() != null) { 204 if (solution.getModel().variables().size() == solution.getAssignment().nrAssignedVariables()) { 205 if (solution.getModel().perturbVariables(solution.getAssignment()).size() <= iMPPLimit) 206 iMPPLimit = solution.getModel().perturbVariables(solution.getAssignment()).size() - 1; 207 } 208 if (iMPPLimit >= 0 && solution.getModel().perturbVariables(solution.getAssignment()).size() > iMPPLimit) 209 return selectedVariable.getInitialAssignment(); 210 if (selectedVariable.getInitialAssignment() != null && ToolBox.random() <= iInitialSelectionProb) 211 return selectedVariable.getInitialAssignment(); 212 } 213 } 214 215 T oldValue = solution.getAssignment().getValue(selectedVariable); 216 List<T> values = selectedVariable.values(solution.getAssignment()); 217 if (ToolBox.random() <= iRandomWalkProb) 218 return ToolBox.random(values); 219 if (iProp != null && oldValue == null && ToolBox.random() <= iGoodSelectionProb) { 220 Collection<T> goodValues = iProp.goodValues(solution.getAssignment(), selectedVariable); 221 if (!goodValues.isEmpty()) 222 values = new ArrayList<T>(goodValues); 223 } 224 if (values.size() == 1) 225 return values.get(0); 226 227 List<T> bestValues = null; 228 double bestWeightedSum = 0; 229 230 for (T value : values) { 231 if (iTabu != null && iTabu.contains(value)) 232 continue; 233 if (oldValue != null && oldValue.equals(value)) 234 continue; 235 236 Collection<T> conf = solution.getModel().conflictValues(solution.getAssignment(), value); 237 if (conf.contains(value)) 238 continue; 239 240 double weightedConflicts = (iStat == null || iWeightWeightedCoflicts == 0.0 ? 0.0 : iStat.countRemovals(solution.getIteration(), conf, value)); 241 double potentialConflicts = (iStat == null || iWeightPotentialConflicts == 0.0 ? 0.0 : iStat.countPotentialConflicts(solution.getAssignment(), solution.getIteration(), value, 3)); 242 243 long deltaInitialAssignments = 0; 244 if (iMPP && iWeightDeltaInitialAssignment != 0.0) { 245 if (iViolatedInitials != null) { 246 Set<T> violations = iViolatedInitials.getViolatedInitials(value); 247 if (violations != null) { 248 for (T aValue : violations) { 249 T aOld = solution.getAssignment().getValue(aValue.variable()); 250 if (aOld == null || aOld.equals(aValue)) 251 deltaInitialAssignments += 2; 252 } 253 } 254 } 255 for (Iterator<T> it1 = conf.iterator(); it1.hasNext();) { 256 T aValue = it1.next(); 257 if (aValue.variable().getInitialAssignment() != null) 258 deltaInitialAssignments--; 259 } 260 if (selectedVariable.getInitialAssignment() != null 261 && !selectedVariable.getInitialAssignment().equals(value)) { 262 deltaInitialAssignments++; 263 } 264 if (iMPPLimit >= 0 && (solution.getModel().perturbVariables(solution.getAssignment()).size() + deltaInitialAssignments) > iMPPLimit) 265 continue; 266 } 267 268 double weightedSum = (iWeightDeltaInitialAssignment * deltaInitialAssignments) 269 + (iWeightPotentialConflicts * potentialConflicts) + (iWeightWeightedCoflicts * weightedConflicts) 270 + (iWeightCoflicts * conf.size()) + (iWeightValue * value.toDouble(solution.getAssignment())); 271 272 if (bestValues == null || bestWeightedSum > weightedSum) { 273 bestWeightedSum = weightedSum; 274 if (bestValues == null) 275 bestValues = new ArrayList<T>(); 276 else 277 bestValues.clear(); 278 bestValues.add(value); 279 } else { 280 if (bestWeightedSum == weightedSum) 281 bestValues.add(value); 282 } 283 } 284 285 T selectedValue = (bestValues == null ? null : ToolBox.random(bestValues)); 286 if (selectedValue == null) 287 selectedValue = ToolBox.random(values); 288 if (iTabu != null) { 289 if (iTabu.size() == iTabuPos) 290 iTabu.add(selectedValue); 291 else 292 iTabu.set(iTabuPos, selectedValue); 293 iTabuPos = (iTabuPos + 1) % iTabuSize; 294 } 295 return (bestValues == null ? null : selectedValue); 296 } 297 298}