    001    package ifs.dbt;
    002
    003
    004    import ifs.extension.*;
    005    import ifs.heuristics.*;
    006    import ifs.model.*;
    007    import ifs.solution.*;
    008    import ifs.solver.*;
    009    import ifs.util.*;
    010    import java.util.*;
    011
    012    /**
    013     * Selection of a value for dynamic backtracking.
    014     * <br><br>
    015     * <li>Returns null if all values of the selected variable are nogood.
    016     * <li>Selected the best good value (according to the parameters) of the selected variable.
    017     * <br><br>
    018     * It is based on a weighted sum of several criteria.
    019     * <br><br>
    020     * This IFS solver value selection heuristics is to be used only in case of dynamic backtracking and it has the following parameters:
    021     * <br>
    022     * <table border='1'><tr><th>Parameter</th><th>Type</th><th>Comment</th></tr>
    023     * <tr><td>General.MPP</td><td>{@link Boolean}</td><td>Minimal Perturbation Problem</td></tr>
    024     * <tr><td>Value.MPPLimit</td><td>{@link Integer}</td><td>Limit on the number of perturbations (only in case of MPP, i.e., when General.MPP=true). MPP limit is decreased when a complete solution is found. If set to -1, it is no used</td></tr>
    025     * <tr><td>Value.InitialSelectionProb</td><td>{@link Double}</td><td>Probability of selection of initial value (only in case of MPP)</td></tr>
    026     * <tr><td>Value.WeightDeltaInitialAssignments</td><td>{@link Double}</td><td>Weight of difference in the number of assignments of initial values in case of selection of the value(only in case of MPP)</td></tr>
    027     * <tr><td>Value.RandomWalkProb</td><td>{@link Double}</td><td>Probability of random selection of a good value</td></tr>
    028     * <tr><td>Value.WeightNrAssignments</td><td>{@link Double}</td><td>Weight of the number of previous assignments of the value</td></tr>
    029     * <tr><td>Value.WeightValue</td><td>{@link Double}</td><td>Weight of the value itself (e.g., for minCSP)</td></tr>
    030     * </table>
    031     * <br>
    032     *
    033     * @author <a href="mailto:muller@ktiml.mff.cuni.cz">Tomáš Müller</a>
    034     * @version 1.0
    035     */
    036    public class DbtValueSelection implements ValueSelection {
    037        private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(GeneralValueSelection.class);
    038        private double iRandomWalkProb = 0.0;
    039        private double iInitialSelectionProb = 0.0;
    040        private int    iMPPLimit = -1;
    041
    042        private double iWeightDeltaInitialAssignment = 0.0;
    043        private double iWeightNrAssignments = 0.5;
    044        private double iWeightValue = 0.0;
    045
    046        private boolean iMPP = false;
    047        private DbtPropagation iProp = null;
    048        private ViolatedInitials iViolatedInitials = null;
    049
    050        public DbtValueSelection(DataProperties properties) {
    051            iMPP = properties.getPropertyBoolean("General.MPP", false);
    052
    053            if (iMPP) {
    054                iMPPLimit = properties.getPropertyInt("Value.MPPLimit", -1);
    055                iInitialSelectionProb = properties.getPropertyDouble("Value.InitialSelectionProb",0.75);
    056                iWeightDeltaInitialAssignment = properties.getPropertyDouble("Value.WeightDeltaInitialAssignments",0.0);
    057            }
    058
    059            iRandomWalkProb = properties.getPropertyDouble("Value.RandomWalkProb",0.0);
    060            iWeightNrAssignments = properties.getPropertyDouble("Value.WeightNrAssignments",0.5);
    061            iWeightValue = properties.getPropertyDouble("Value.WeightValue", 0.0);
    062        }
    063
    064        /**
    065         * Heuristics initialization
    066         *
    067         * @see ValueSelection#init(Solver)
    068         */
    069        public void init(Solver solver) {
    070            for (Enumeration i = solver.getExtensions().elements(); i.hasMoreElements();) {
    071                Extension extension = (Extension) i.nextElement();
    072
    073                if (extension instanceof DbtPropagation) {
    074                    iProp = (DbtPropagation) extension;
    075                }
    076                if (extension instanceof ViolatedInitials) {
    077                    iViolatedInitials = (ViolatedInitials) extension;
    078                }
    079            }
    080        }
    081
    082        /**
    083         * Value selection
    084         *
    085         * @see ValueSelection#selectValue(Solution, Variable)
    086         */
    087        public Value selectValue(Solution solution, Variable selectedVariable) {
    088            Vector values = null;
    089
    090            if (iProp != null) {
    091                values = new FastVector(iProp.goodValues(selectedVariable).size());
    092                for (Enumeration i1 = selectedVariable.values().elements(); i1.hasMoreElements();) {
    093                    Value value = (Value) i1.nextElement();
    094
    095                    if (!iProp.isGood(value)) {
    096                        continue;
    097                    }
    098                    Collection conf = solution.getModel().conflictValues(value);
    099
    100                    if (!conf.isEmpty()) {
    101                        HashSet noGood = new HashSet(2 * conf.size());
    102
    103                        for (Iterator i2 = conf.iterator(); i2.hasNext();) {
    104                            noGood.add((Value) i2.next());
    105                        }
    106                        iProp.setNoGood(value, noGood);
    107                        sLogger.debug(value+" become nogood ("+noGood+")");
    108                    } else {
    109                        if (!solution.isBestComplete() || solution.getBestValue()> solution.getModel().getTotalValue()+value.toInt()) {
    110                            values.add(value);
    111                        }
    112                    }
    113                }
    114            } else {
    115                values = new FastVector(selectedVariable.values().size());
    116                for (Enumeration i1 = selectedVariable.values().elements(); i1.hasMoreElements();) {
    117                    Value value = (Value) i1.nextElement();
    118
    119                    if (solution.getModel().conflictValues(value).isEmpty()) {
    120                        if (solution.isBestComplete() && solution.getBestValue()>solution.getModel().getTotalValue()+value.toInt()) {
    121                            values.add(value);
    122                        }
    123                    }
    124                }
    125            }
    126            if (values.isEmpty()) {
    127                return null;
    128            }
    129
    130            if (iMPP) {
    131                if (iMPPLimit>=0 && solution.isBestComplete() && solution.getBestPertirbations()>=0 && solution.getBestPertirbations() <= iMPPLimit) {
    132                    iMPPLimit = solution.getBestPertirbations() - 1;
    133                    sLogger.debug("MPP Limit decreased to "+iMPPLimit);
    134                }
    135
    136                int nrPerts = solution.getModel().perturbVariables().size();
    137
    138                if (iMPPLimit>=0 && iMPPLimit < nrPerts) {
    139                    return null;
    140                }
    141                if (iMPPLimit>=0 && iMPPLimit==nrPerts && selectedVariable.getInitialAssignment() != null) {
    142                    if (values.contains(selectedVariable.getInitialAssignment())) {
    143                        return selectedVariable.getInitialAssignment();
    144                    } else {
    145                        return null;
    146                    }
    147                }
    148
    149                if (selectedVariable.getInitialAssignment() != null && ToolBox.random() <= iInitialSelectionProb) {
    150                    if (values.contains(selectedVariable.getInitialAssignment())) {
    151                        return selectedVariable.getInitialAssignment();
    152                    }
    153                }
    154            }
    155
    156            if (values.size()==1) {
    157                return (Value) values.firstElement();
    158            }
    159
    160            if (ToolBox.random() <= iRandomWalkProb) {
    161                return (Value) ToolBox.random(values);
    162            }
    163
    164            Vector bestValues = null;
    165            double bestWeightedSum = 0;
    166
    167            if (iWeightDeltaInitialAssignment==0.0 && iWeightNrAssignments==0.0 && iWeightValue==0.0) {
    168                return (Value) ToolBox.random(values);
    169            }
    170
    171            for (Enumeration i1 = values.elements(); i1.hasMoreElements();) {
    172                Value value = (Value) i1.nextElement();
    173
    174                long deltaInitialAssignments = 0;
    175
    176                if (iWeightDeltaInitialAssignment != 0.0) {
    177                    if (iViolatedInitials != null) {
    178                        Set violations = iViolatedInitials.getViolatedInitials(value);
    179
    180                        if (violations != null) {
    181                            for (Iterator it1 = violations.iterator(); it1.hasNext();) {
    182                                Value aValue = (Value) it1.next();
    183
    184                                if (aValue.variable().getAssignment()==null || aValue.variable().getAssignment().equals(aValue)) {
    185                                    deltaInitialAssignments += 2;
    186                                }
    187                            }
    188                        }
    189                    }
    190                    if (selectedVariable.getInitialAssignment() != null && !selectedVariable.getInitialAssignment().equals(value)) {
    191                        deltaInitialAssignments++;
    192                    }
    193                    if (iMPPLimit>=0 && (solution.getModel().perturbVariables().size()+deltaInitialAssignments)>iMPPLimit) {
    194                        continue;
    195                    }
    196                }
    197
    198                double weightedSum =
    199                      (iWeightDeltaInitialAssignment * deltaInitialAssignments)
    200                    + (iWeightNrAssignments * value.countAssignments())
    201                    + (iWeightValue * value.toInt());
    202
    203                if (bestValues==null || bestWeightedSum>weightedSum) {
    204                    bestWeightedSum = weightedSum;
    205                    if (bestValues==null) {
    206                        bestValues = new FastVector();
    207                    } else {
    208                        bestValues.clear();
    209                    }
    210                    bestValues.addElement(value);
    211                } else if (bestWeightedSum==weightedSum) {
    212                    bestValues.addElement(value);
    213                }
    214            }
    215            return (bestValues==null ? null : (Value) ToolBox.random(bestValues));
    216        }
    217    }