001package net.sf.cpsolver.ifs.heuristics; 002 003import java.util.ArrayList; 004import java.util.Iterator; 005import java.util.List; 006import java.util.Set; 007 008import net.sf.cpsolver.ifs.extension.Extension; 009import net.sf.cpsolver.ifs.extension.MacPropagation; 010import net.sf.cpsolver.ifs.model.Value; 011import net.sf.cpsolver.ifs.model.Variable; 012import net.sf.cpsolver.ifs.solution.Solution; 013import net.sf.cpsolver.ifs.solver.Solver; 014import net.sf.cpsolver.ifs.util.DataProperties; 015import net.sf.cpsolver.ifs.util.ToolBox; 016 017/** 018 * General implementation of variable selection criterion. <br> 019 * <br> 020 * In case that all variables are assigned, one of the variables is selected 021 * randomly. In case of MPP, the random selection is made among the variables 022 * which have not assigned initial values. <br> 023 * <br> 024 * When there are unassigned variables, a variable is selected randomly among 025 * all unassigned variables (when Variable.RandomSelection is true) or the 026 * following roulette wheel selection takes place (MPP): 027 * <ul> 028 * <li>one point for a variable with no initial assignment 029 * <li>3 * ( 1 + number of conflicts with the initial assignment) for a variable 030 * with an initial assignment 031 * </ul> 032 * <br> 033 * If {@link MacPropagation} is used and Variable.UnassignWhenNoGood parameter 034 * is true, while there is a variable with an empty domain: 035 * <ul> 036 * <li>with Variable.UnassignWhenNoGoodRandomWalk probabilty an arbitrary 037 * assigned variable is selected 038 * <li>otherwise, one variable with empty domain is picked, one of its original 039 * values is picked and one of the variables from the explanation of that value 040 * is then returned. If the explanation is empty, another variable and value is 041 * tried (up to ten times). 042 * </ul> 043 * <br> 044 * Parameters: <br> 045 * <table border='1'> 046 * <tr> 047 * <th>Parameter</th> 048 * <th>Type</th> 049 * <th>Comment</th> 050 * </tr> 051 * <tr> 052 * <td>Variable.RandomSelection</td> 053 * <td>{@link Boolean}</td> 054 * <td>if true, an unassigned variable is picked randomly</td> 055 * </tr> 056 * <tr> 057 * <td>Variable.UnassignWhenNoGood</td> 058 * <td>{@link Boolean}</td> 059 * <td>if true and if {@link MacPropagation} is used: if there is a variable 060 * with empty domain, assigned variable (which is present in some explanation 061 * for a vairable with empty domain) is selected (for reassignment)</td> 062 * </tr> 063 * <tr> 064 * <td>Variable.UnassignWhenNoGoodRandomWalk</td> 065 * <td>{@link Double}</td> 066 * <td>if Variable.UnassignWhenNoGood is true and if {@link MacPropagation} is 067 * used: if there is a variable with empty domain, with the given probability an 068 * arbitrary assigned variable is selected</td> 069 * </tr> 070 * </table> 071 * 072 * @see VariableSelection 073 * @see Solver 074 * 075 * @version IFS 1.2 (Iterative Forward Search)<br> 076 * Copyright (C) 2006 - 2010 Tomáš Müller<br> 077 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 078 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 079 * <br> 080 * This library is free software; you can redistribute it and/or modify 081 * it under the terms of the GNU Lesser General Public License as 082 * published by the Free Software Foundation; either version 3 of the 083 * License, or (at your option) any later version. <br> 084 * <br> 085 * This library is distributed in the hope that it will be useful, but 086 * WITHOUT ANY WARRANTY; without even the implied warranty of 087 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 088 * Lesser General Public License for more details. <br> 089 * <br> 090 * You should have received a copy of the GNU Lesser General Public 091 * License along with this library; if not see <http://www.gnu.org/licenses/>. 092 **/ 093public class GeneralVariableSelection<V extends Variable<V, T>, T extends Value<V, T>> implements 094 VariableSelection<V, T> { 095 private boolean iUnassignWhenNotGood = false; 096 private double iUnassignWhenNotGoodRandWalk = 0.02; 097 private boolean iRandomSelection = true; 098 099 private MacPropagation<V, T> iProp = null; 100 101 /** 102 * Constructor 103 * 104 * @param properties 105 * input configuration 106 */ 107 public GeneralVariableSelection(DataProperties properties) { 108 iUnassignWhenNotGood = properties.getPropertyBoolean("Variable.UnassignWhenNoGood", iUnassignWhenNotGood); 109 iUnassignWhenNotGoodRandWalk = properties.getPropertyDouble("Variable.UnassignWhenNoGoodRandomWalk", 110 iUnassignWhenNotGoodRandWalk); 111 iRandomSelection = properties.getPropertyBoolean("Variable.RandomSelection", iRandomSelection); 112 } 113 114 public GeneralVariableSelection() { 115 } 116 117 /** Initialization */ 118 @Override 119 public void init(Solver<V, T> solver) { 120 for (Extension<V, T> extension : solver.getExtensions()) { 121 if (MacPropagation.class.isInstance(extension)) 122 iProp = (MacPropagation<V, T>) extension; 123 } 124 } 125 126 /** Variable selection */ 127 @Override 128 public V selectVariable(Solution<V, T> solution) { 129 if (solution.getModel().nrUnassignedVariables() == 0) { 130 if (!solution.getModel().perturbVariables().isEmpty()) 131 return ToolBox.random(solution.getModel().perturbVariables()); 132 else 133 return ToolBox.random(solution.getModel().assignedVariables()); 134 } else { 135 if (iProp != null && iUnassignWhenNotGood) { 136 List<V> noGoodVariables = new ArrayList<V>(); 137 for (V variable : solution.getModel().unassignedVariables()) { 138 if (iProp.goodValues(variable).isEmpty()) 139 noGoodVariables.add(variable); 140 } 141 if (!noGoodVariables.isEmpty()) { 142 if (ToolBox.random() < iUnassignWhenNotGoodRandWalk) 143 return ToolBox.random(solution.getModel().assignedVariables()); 144 for (int attempt = 0; attempt < 10; attempt++) { 145 V noGoodVariable = ToolBox.random(noGoodVariables); 146 T noGoodValue = ToolBox.random(noGoodVariable.values()); 147 Set<T> noGood = iProp.noGood(noGoodValue); 148 if (noGood != null && !noGood.isEmpty()) 149 return ToolBox.random(noGood).variable(); 150 } 151 } 152 } 153 if (iRandomSelection) 154 return ToolBox.random(solution.getModel().unassignedVariables()); 155 List<Integer> points = new ArrayList<Integer>(); 156 int totalPoints = 0; 157 for (V variable : solution.getModel().unassignedVariables()) { 158 int pointsThisVariable = (variable.getInitialAssignment() != null ? 3 * (1 + solution.getModel() 159 .conflictValues(variable.getInitialAssignment()).size()) : 1); 160 totalPoints += pointsThisVariable; 161 points.add(totalPoints); 162 } 163 int rndPoints = ToolBox.random(totalPoints); 164 Iterator<V> x = solution.getModel().unassignedVariables().iterator(); 165 for (int i = 0; x.hasNext() && i < points.size(); i++) { 166 V variable = x.next(); 167 int tp = points.get(i); 168 if (tp > rndPoints) 169 return variable; 170 } 171 return ToolBox.random(solution.getModel().unassignedVariables()); 172 } 173 } 174 175}