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