    001    package ifs.heuristics;
    002
    003    import ifs.extension.*;
    004    import ifs.model.*;
    005    import ifs.solution.*;
    006    import ifs.solver.*;
    007    import ifs.util.*;
    008
    009    import java.util.*;
    010
    011    /**
    012     * General implementation of variable selection criterion.
    013     * <br><br>
    014     * In case that all variables are assigned, one of the variables is selected randomly. In case of MPP,
    015     * the random selection is made among the variables which have not assigned initial values.
    016     * <br><br>
    017     * When there are unassigned variables, a variable is selected randomly among all
    018     * unassigned variables (when Variable.RandomSelection is true) or the following roulette
    019     * wheel selection takes place (MPP):<ul>
    020     * <li> one point for a variable with no initial assignment
    021     * <li> 3 * ( 1 + number of conflicts with the initial assignment) for a variable with an initial assignment
    022     * </ul>
    023     * <br>
    024     * If {@link MacPropagation} is used and Variable.UnassignWhenNoGood parameter is true, while
    025     * there is a variable with an empty domain: <ul>
    026     * <li> with Variable.UnassignWhenNoGoodRandomWalk probabilty an arbitrary assigned variable is selected
    027     * <li> otherwise, one variable with empty domain is picked, one of its original values is picked and
    028     * one of the variables from the explanation of that value is then returned. If the explanation is
    029     * empty, another variable and value is tried (up to ten times).
    030     * </ul>
    031     * <br>
    032     * Parameters:
    033     * <br>
    034     * <table border='1'><tr><th>Parameter</th><th>Type</th><th>Comment</th></tr>
    035     * <tr><td>Variable.RandomSelection</td><td>{@link Boolean}</td><td>if true, an unassigned variable is picked randomly</td></tr>
    036     * <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>
    037     * <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>
    038     * </table>
    039     *
    040     * @see VariableSelection
    041     * @see Solver
    042     *
    043     * @author <a href="mailto:muller@ktiml.mff.cuni.cz">Tomáš Müller</a>
    044     * @version 1.0
    045     **/
    046    public class GeneralVariableSelection implements VariableSelection {
    047        private boolean iUnassignWhenNotGood = false;
    048        private double iUnassignWhenNotGoodRandWalk = 0.02;
    049        private boolean iRandomSelection = true;
    050
    051        private boolean iMPP = false;
    052        private MacPropagation iProp = null;
    053
    054        /** Constructor
    055         * @param properties input configuration
    056         */
    057        public GeneralVariableSelection(DataProperties properties) {
    058            iUnassignWhenNotGood = properties.getPropertyBoolean("Variable.UnassignWhenNoGood", iUnassignWhenNotGood);
    059            iUnassignWhenNotGoodRandWalk = properties.getPropertyDouble("Variable.UnassignWhenNoGoodRandomWalk", iUnassignWhenNotGoodRandWalk);
    060            iRandomSelection = properties.getPropertyBoolean("Variable.RandomSelection", iRandomSelection);
    061        }
    062
    063        public GeneralVariableSelection() {
    064        }
    065
    066        /** Initialization */
    067        public void init(Solver solver) {
    068            for (Enumeration i = solver.getExtensions().elements(); i.hasMoreElements(); ) {
    069                Extension extension = (Extension)i.nextElement();
    070                if (extension instanceof MacPropagation) iProp = (MacPropagation)extension;
    071            }
    072        }
    073
    074        /** Variable selection */
    075        public Variable selectVariable(Solution solution) {
    076            if (solution.getModel().unassignedVariables().isEmpty()) {
    077                if (!solution.getModel().perturbVariables().isEmpty())
    078                    return (Variable)ToolBox.random(solution.getModel().perturbVariables());
    079                else
    080                    return (Variable)ToolBox.random(solution.getModel().assignedVariables());
    081            } else {
    082                if (iProp != null && iUnassignWhenNotGood) {
    083                    Vector noGoodVariables = new FastVector();
    084                    for (Enumeration i1 = solution.getModel().unassignedVariables().elements(); i1.hasMoreElements();) {
    085                        Variable variable = (Variable)i1.nextElement();
    086                        if (iProp.goodValues(variable).isEmpty())
    087                            noGoodVariables.addElement(variable);
    088                    }
    089                    if (!noGoodVariables.isEmpty()) {
    090                        if (ToolBox.random() < iUnassignWhenNotGoodRandWalk)
    091                            return (Variable)ToolBox.random(solution.getModel().assignedVariables());
    092                        for (int attempt = 0; attempt < 10; attempt++) {
    093                            Variable noGoodVariable = (Variable)ToolBox.random(noGoodVariables);
    094                            Value noGoodValue = (Value)ToolBox.random(noGoodVariable.values());
    095                            Set noGood = iProp.noGood(noGoodValue);
    096                            if (noGood!=null && !noGood.isEmpty())
    097                                return ((Value)ToolBox.random(noGood)).variable();
    098                        }
    099                    }
    100                }
    101                if (iRandomSelection)
    102                    return (Variable)ToolBox.random(solution.getModel().unassignedVariables());
    103                Vector points = new FastVector();
    104                int totalPoints = 0;
    105                for (Enumeration i = solution.getModel().unassignedVariables().elements(); i.hasMoreElements(); ) {
    106                    Variable variable = (Variable)i.nextElement();
    107                    int pointsThisVariable = (variable.getInitialAssignment()!=null ? 3*(1+solution.getModel().conflictValues(variable.getInitialAssignment()).size()):1);
    108                    totalPoints += pointsThisVariable;
    109                    points.addElement(new Integer(totalPoints));
    110                }
    111                int rndPoints = ToolBox.random(totalPoints);
    112                Enumeration x = solution.getModel().unassignedVariables().elements();
    113                for (int i = 0; x.hasMoreElements() && i < points.size(); i++) {
    114                    Variable variable = (Variable)x.nextElement();
    115                    int tp = ((Integer)points.elementAt(i)).intValue();
    116                    if (tp > rndPoints) return variable;
    117                }
    118                return (Variable)ToolBox.random(solution.getModel().unassignedVariables());
    119            }
    120        }
    121
    122    }