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    }