    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}