001    package net.sf.cpsolver.ifs.dbt;
002    
003    import java.util.ArrayList;
004    import java.util.Collection;
005    import java.util.HashSet;
006    import java.util.Set;
007    
008    import net.sf.cpsolver.ifs.extension.Extension;
009    import net.sf.cpsolver.ifs.extension.ViolatedInitials;
010    import net.sf.cpsolver.ifs.heuristics.GeneralValueSelection;
011    import net.sf.cpsolver.ifs.heuristics.ValueSelection;
012    import net.sf.cpsolver.ifs.model.Value;
013    import net.sf.cpsolver.ifs.model.Variable;
014    import net.sf.cpsolver.ifs.solution.Solution;
015    import net.sf.cpsolver.ifs.solver.Solver;
016    import net.sf.cpsolver.ifs.util.DataProperties;
017    import net.sf.cpsolver.ifs.util.ToolBox;
018    
019    /**
020     * Selection of a value for dynamic backtracking. <br>
021     * <br>
022     * <li>Returns null if all values of the selected variable are nogood. <li>
023     * Selected the best good value (according to the parameters) of the selected
024     * variable. <br>
025     * <br>
026     * It is based on a weighted sum of several criteria. <br>
027     * <br>
028     * This IFS solver value selection heuristics is to be used only in case of
029     * dynamic backtracking and it has the following parameters: <br>
030     * <table border='1'>
031     * <tr>
032     * <th>Parameter</th>
033     * <th>Type</th>
034     * <th>Comment</th>
035     * </tr>
036     * <tr>
037     * <td>General.MPP</td>
038     * <td>{@link Boolean}</td>
039     * <td>Minimal Perturbation Problem</td>
040     * </tr>
041     * <tr>
042     * <td>Value.MPPLimit</td>
043     * <td>{@link Integer}</td>
044     * <td>Limit on the number of perturbations (only in case of MPP, i.e., when
045     * General.MPP=true). MPP limit is decreased when a complete solution is found.
046     * If set to -1, it is no used</td>
047     * </tr>
048     * <tr>
049     * <td>Value.InitialSelectionProb</td>
050     * <td>{@link Double}</td>
051     * <td>Probability of selection of initial value (only in case of MPP)</td>
052     * </tr>
053     * <tr>
054     * <td>Value.WeightDeltaInitialAssignments</td>
055     * <td>{@link Double}</td>
056     * <td>Weight of difference in the number of assignments of initial values in
057     * case of selection of the value(only in case of MPP)</td>
058     * </tr>
059     * <tr>
060     * <td>Value.RandomWalkProb</td>
061     * <td>{@link Double}</td>
062     * <td>Probability of random selection of a good value</td>
063     * </tr>
064     * <tr>
065     * <td>Value.WeightNrAssignments</td>
066     * <td>{@link Double}</td>
067     * <td>Weight of the number of previous assignments of the value</td>
068     * </tr>
069     * <tr>
070     * <td>Value.WeightValue</td>
071     * <td>{@link Double}</td>
072     * <td>Weight of the value itself (e.g., for minCSP)</td>
073     * </tr>
074     * </table>
075     * <br>
076     * 
077     * @version IFS 1.2 (Iterative Forward Search)<br>
078     *          Copyright (C) 2006 - 2010 Tomas Muller<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
094     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
095     */
096    public class DbtValueSelection<V extends Variable<V, T>, T extends Value<V, T>> implements ValueSelection<V, T> {
097        private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(GeneralValueSelection.class);
098        private double iRandomWalkProb = 0.0;
099        private double iInitialSelectionProb = 0.0;
100        private int iMPPLimit = -1;
101    
102        private double iWeightDeltaInitialAssignment = 0.0;
103        private double iWeightNrAssignments = 0.5;
104        private double iWeightValue = 0.0;
105    
106        private boolean iMPP = false;
107        private DbtPropagation<V, T> iProp = null;
108        private ViolatedInitials<V, T> iViolatedInitials = null;
109    
110        public DbtValueSelection(DataProperties properties) {
111            iMPP = properties.getPropertyBoolean("General.MPP", false);
112    
113            if (iMPP) {
114                iMPPLimit = properties.getPropertyInt("Value.MPPLimit", -1);
115                iInitialSelectionProb = properties.getPropertyDouble("Value.InitialSelectionProb", 0.75);
116                iWeightDeltaInitialAssignment = properties.getPropertyDouble("Value.WeightDeltaInitialAssignments", 0.0);
117            }
118    
119            iRandomWalkProb = properties.getPropertyDouble("Value.RandomWalkProb", 0.0);
120            iWeightNrAssignments = properties.getPropertyDouble("Value.WeightNrAssignments", 0.5);
121            iWeightValue = properties.getPropertyDouble("Value.WeightValue", 0.0);
122        }
123    
124        /**
125         * Heuristics initialization
126         * 
127         * @see ValueSelection#init(Solver)
128         */
129        @Override
130        public void init(Solver<V, T> solver) {
131            for (Extension<V, T> extension : solver.getExtensions()) {
132                if (DbtPropagation.class.isInstance(extension)) {
133                    iProp = (DbtPropagation<V, T>) extension;
134                }
135                if (ViolatedInitials.class.isInstance(extension)) {
136                    iViolatedInitials = (ViolatedInitials<V, T>) extension;
137                }
138            }
139        }
140    
141        /**
142         * Value selection
143         * 
144         * @see ValueSelection#selectValue(Solution, Variable)
145         */
146        @Override
147        public T selectValue(Solution<V, T> solution, V selectedVariable) {
148            ArrayList<T> values = null;
149    
150            if (iProp != null) {
151                values = new ArrayList<T>(iProp.goodValues(selectedVariable).size());
152                for (T value : selectedVariable.values()) {
153                    if (!iProp.isGood(value)) {
154                        continue;
155                    }
156                    Collection<T> conf = solution.getModel().conflictValues(value);
157    
158                    if (!conf.isEmpty()) {
159                        Set<T> noGood = new HashSet<T>(2 * conf.size());
160    
161                        for (T v : conf) {
162                            noGood.add(v);
163                        }
164                        iProp.setNoGood(value, noGood);
165                        sLogger.debug(value + " become nogood (" + noGood + ")");
166                    } else {
167                        if (!solution.isBestComplete()
168                                || solution.getBestValue() > solution.getModel().getTotalValue() + value.toDouble()) {
169                            values.add(value);
170                        }
171                    }
172                }
173            } else {
174                values = new ArrayList<T>(selectedVariable.values().size());
175                for (T value : selectedVariable.values()) {
176                    if (solution.getModel().conflictValues(value).isEmpty()) {
177                        if (solution.isBestComplete()
178                                && solution.getBestValue() > solution.getModel().getTotalValue() + value.toDouble()) {
179                            values.add(value);
180                        }
181                    }
182                }
183            }
184            if (values.isEmpty()) {
185                return null;
186            }
187    
188            if (iMPP) {
189                if (iMPPLimit >= 0 && solution.isBestComplete() && solution.getModel().getBestPerturbations() >= 0
190                        && solution.getModel().getBestPerturbations() <= iMPPLimit) {
191                    iMPPLimit = solution.getModel().getBestPerturbations() - 1;
192                    sLogger.debug("MPP Limit decreased to " + iMPPLimit);
193                }
194    
195                int nrPerts = solution.getModel().perturbVariables().size();
196    
197                if (iMPPLimit >= 0 && iMPPLimit < nrPerts) {
198                    return null;
199                }
200                if (iMPPLimit >= 0 && iMPPLimit == nrPerts && selectedVariable.getInitialAssignment() != null) {
201                    if (values.contains(selectedVariable.getInitialAssignment())) {
202                        return selectedVariable.getInitialAssignment();
203                    }
204                    return null;
205                }
206    
207                if (selectedVariable.getInitialAssignment() != null && ToolBox.random() <= iInitialSelectionProb) {
208                    if (values.contains(selectedVariable.getInitialAssignment())) {
209                        return selectedVariable.getInitialAssignment();
210                    }
211                }
212            }
213    
214            if (values.size() == 1) {
215                return values.get(0);
216            }
217    
218            if (ToolBox.random() <= iRandomWalkProb) {
219                return ToolBox.random(values);
220            }
221    
222            ArrayList<T> bestValues = null;
223            double bestWeightedSum = 0;
224    
225            if (iWeightDeltaInitialAssignment == 0.0 && iWeightNrAssignments == 0.0 && iWeightValue == 0.0) {
226                return ToolBox.random(values);
227            }
228    
229            for (T value : values) {
230    
231                long deltaInitialAssignments = 0;
232    
233                if (iWeightDeltaInitialAssignment != 0.0) {
234                    if (iViolatedInitials != null) {
235                        Set<T> violations = iViolatedInitials.getViolatedInitials(value);
236    
237                        if (violations != null) {
238                            for (T aValue : violations) {
239                                if (aValue.variable().getAssignment() == null
240                                        || aValue.variable().getAssignment().equals(aValue)) {
241                                    deltaInitialAssignments += 2;
242                                }
243                            }
244                        }
245                    }
246                    if (selectedVariable.getInitialAssignment() != null
247                            && !selectedVariable.getInitialAssignment().equals(value)) {
248                        deltaInitialAssignments++;
249                    }
250                    if (iMPPLimit >= 0
251                            && (solution.getModel().perturbVariables().size() + deltaInitialAssignments) > iMPPLimit) {
252                        continue;
253                    }
254                }
255    
256                double weightedSum = (iWeightDeltaInitialAssignment * deltaInitialAssignments)
257                        + (iWeightNrAssignments * value.countAssignments()) + (iWeightValue * value.toDouble());
258    
259                if (bestValues == null || bestWeightedSum > weightedSum) {
260                    bestWeightedSum = weightedSum;
261                    if (bestValues == null) {
262                        bestValues = new ArrayList<T>();
263                    } else {
264                        bestValues.clear();
265                    }
266                    bestValues.add(value);
267                } else if (bestWeightedSum == weightedSum) {
268                    bestValues.add(value);
269                }
270            }
271            return (bestValues == null ? null : (T) ToolBox.random(bestValues));
272        }
273    }