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