001 package net.sf.cpsolver.ifs.heuristics;
002
003 import java.util.ArrayList;
004 import java.util.Iterator;
005 import java.util.List;
006 import java.util.Set;
007
008 import net.sf.cpsolver.ifs.extension.Extension;
009 import net.sf.cpsolver.ifs.extension.MacPropagation;
010 import net.sf.cpsolver.ifs.model.Value;
011 import net.sf.cpsolver.ifs.model.Variable;
012 import net.sf.cpsolver.ifs.solution.Solution;
013 import net.sf.cpsolver.ifs.solver.Solver;
014 import net.sf.cpsolver.ifs.util.DataProperties;
015 import 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 Tomas Muller<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 **/
093 public 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 }