001    package net.sf.cpsolver.ifs.heuristics;
002    
003    import java.util.ArrayList;
004    import java.util.Collection;
005    import java.util.Iterator;
006    import java.util.List;
007    import java.util.Set;
008    
009    import net.sf.cpsolver.ifs.extension.ConflictStatistics;
010    import net.sf.cpsolver.ifs.extension.Extension;
011    import net.sf.cpsolver.ifs.extension.MacPropagation;
012    import net.sf.cpsolver.ifs.extension.ViolatedInitials;
013    import net.sf.cpsolver.ifs.model.Model;
014    import net.sf.cpsolver.ifs.model.Value;
015    import net.sf.cpsolver.ifs.model.Variable;
016    import net.sf.cpsolver.ifs.solution.Solution;
017    import net.sf.cpsolver.ifs.solver.Solver;
018    import net.sf.cpsolver.ifs.util.DataProperties;
019    import net.sf.cpsolver.ifs.util.ToolBox;
020    
021    /**
022     * General implementation of value selection criterion. <br>
023     * <br>
024     * Value selection criterion is based on weighted sum of various criteria. It
025     * also allows random walk technique and tabu search. <br>
026     * Parameters: <br>
027     * <table border='1'>
028     * <tr>
029     * <th>Parameter</th>
030     * <th>Type</th>
031     * <th>Comment</th>
032     * </tr>
033     * <tr>
034     * <td>General.MPP</td>
035     * <td>{@link Boolean}</td>
036     * <td>if true, MPP is being solved</td>
037     * </tr>
038     * <tr>
039     * <td>Value.MPPLimit</td>
040     * <td>{@link Integer}</td>
041     * <td>MPP: limitation of the number of allowed perturbations. If a solution
042     * within this limit is gound, it is decreased.</td>
043     * </tr>
044     * <tr>
045     * <td>Value.InitialSelectionProb</td>
046     * <td>{@link Double}</td>
047     * <td>MPP: probability of selection of the initial value</td>
048     * </tr>
049     * <tr>
050     * <td>Value.RandomWalkProb</td>
051     * <td>{@link Double}</td>
052     * <td>Random Walk: probability of selection of a value randomly among all the
053     * values</td>
054     * </tr>
055     * <tr>
056     * <td>Value.Tabu</td>
057     * <td>{@link Integer}</td>
058     * <td>Tabu Search: length of the tabu-list</td>
059     * </tr>
060     * <tr>
061     * <td>Value.GoodSelectionProb</td>
062     * <td>{@link Double}</td>
063     * <td>In case of {@link MacPropagation}, with this probability (1.0 means
064     * always), the selection is made only among good values (not removed from the
065     * domain).</td>
066     * </tr>
067     * </table>
068     * <br>
069     * Following weights are used in the weighted sum (computed for all values). The
070     * value with the lowest weighted sum is selected. If there are more than one of
071     * such values, one of them is selected randomly. <br>
072     * <table border='1'>
073     * <tr>
074     * <th>Parameter</th>
075     * <th>Type</th>
076     * <th>Comment</th>
077     * </tr>
078     * <tr>
079     * <td>Value.WeightDeltaInitialAssignments</td>
080     * <td>{@link Double}</td>
081     * <td>MPP: Difference in the number of assigned initial values if the value is
082     * assigned to the variable (weighted by this
083     * Value.WeightDeltaInitialAssignments): -1 if the value is initial, 0
084     * otherwise, increased by the number of initial values assigned to variables
085     * with hard conflicts with the value</td>
086     * </tr>
087     * <tr>
088     * <td>Value.WeightWeightedConflicts</td>
089     * <td>{@link Double}</td>
090     * <td>When {@link ConflictStatistics} is used: weighted number of conflicting
091     * variables</td>
092     * </tr>
093     * <tr>
094     * <td>Value.WeightPotentialConflicts</td>
095     * <td>{@link Double}</td>
096     * <td>When {@link ConflictStatistics} is used: weighted number of potentially
097     * conflicting variables</td>
098     * </tr>
099     * <tr>
100     * <td>Value.WeightConflicts</td>
101     * <td>{@link Double}</td>
102     * <td>Number of conflicting variables {@link Model#conflictValues(Value)}.</td>
103     * </tr>
104     * <tr>
105     * <td>Value.WeightNrAssignments</td>
106     * <td>{@link Double}</td>
107     * <td>Number of previous assignments of the value</td>
108     * </tr>
109     * <tr>
110     * <td>Value.WeightValue</td>
111     * <td>{@link Double}</td>
112     * <td>Value {@link Value#toDouble()}</td>
113     * </tr>
114     * </table>
115     * 
116     * @see VariableSelection
117     * @see Solver
118     * 
119     * @version IFS 1.2 (Iterative Forward Search)<br>
120     *          Copyright (C) 2006 - 2010 Tomas Muller<br>
121     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
122     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
123     * <br>
124     *          This library is free software; you can redistribute it and/or modify
125     *          it under the terms of the GNU Lesser General Public License as
126     *          published by the Free Software Foundation; either version 3 of the
127     *          License, or (at your option) any later version. <br>
128     * <br>
129     *          This library is distributed in the hope that it will be useful, but
130     *          WITHOUT ANY WARRANTY; without even the implied warranty of
131     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
132     *          Lesser General Public License for more details. <br>
133     * <br>
134     *          You should have received a copy of the GNU Lesser General Public
135     *          License along with this library; if not see <http://www.gnu.org/licenses/>.
136     **/
137    
138    public class GeneralValueSelection<V extends Variable<V, T>, T extends Value<V, T>> implements ValueSelection<V, T> {
139        private double iRandomWalkProb = 0.0;
140        private double iInitialSelectionProb = 0.0;
141        private double iGoodSelectionProb = 0.0;
142        private int iMPPLimit = -1;
143    
144        private double iWeightDeltaInitialAssignment = 0.0;
145        private double iWeightPotentialConflicts = 0.0;
146        private double iWeightWeightedCoflicts = 0.0;
147        private double iWeightCoflicts = 1.0;
148        private double iWeightNrAssignments = 0.5;
149        private double iWeightValue = 0.0;
150    
151        protected int iTabuSize = 0;
152        protected ArrayList<T> iTabu = null;
153        protected int iTabuPos = 0;
154    
155        private boolean iMPP = false;
156        private ConflictStatistics<V, T> iStat = null;
157        private MacPropagation<V, T> iProp = null;
158        private ViolatedInitials<V, T> iViolatedInitials = null;
159    
160        public GeneralValueSelection() {
161        }
162    
163        /**
164         * Constructor
165         * 
166         * @param properties
167         *            input configuration
168         */
169        public GeneralValueSelection(DataProperties properties) {
170            iMPP = properties.getPropertyBoolean("General.MPP", false);
171            if (iMPP) {
172                iMPPLimit = properties.getPropertyInt("Value.MPPLimit", -1);
173                iInitialSelectionProb = properties.getPropertyDouble("Value.InitialSelectionProb", 0.75);
174                iWeightDeltaInitialAssignment = properties.getPropertyDouble("Value.WeightDeltaInitialAssignments", 0.0);
175            }
176            iGoodSelectionProb = properties.getPropertyDouble("Value.GoodSelectionProb", 0.00);
177            iWeightWeightedCoflicts = properties.getPropertyDouble("Value.WeightWeightedConflicts", 1.0);
178            iWeightPotentialConflicts = properties.getPropertyDouble("Value.WeightPotentialConflicts", 0.0);
179    
180            iRandomWalkProb = properties.getPropertyDouble("Value.RandomWalkProb", 0.0);
181            iWeightCoflicts = properties.getPropertyDouble("Value.WeightConflicts", 1.0);
182            iWeightNrAssignments = properties.getPropertyDouble("Value.WeightNrAssignments", 0.5);
183            iWeightValue = properties.getPropertyDouble("Value.WeightValue", 0.0);
184            iTabuSize = properties.getPropertyInt("Value.Tabu", 0);
185            if (iTabuSize > 0)
186                iTabu = new ArrayList<T>(iTabuSize);
187        }
188    
189        /** Initialization */
190        @Override
191        public void init(Solver<V, T> solver) {
192            for (Extension<V, T> extension : solver.getExtensions()) {
193                if (ConflictStatistics.class.isInstance(extension))
194                    iStat = (ConflictStatistics<V, T>) extension;
195                if (MacPropagation.class.isInstance(extension))
196                    iProp = (MacPropagation<V, T>) extension;
197                if (ViolatedInitials.class.isInstance(extension))
198                    iViolatedInitials = (ViolatedInitials<V, T>) extension;
199            }
200        }
201    
202        /** Value selection */
203        @Override
204        public T selectValue(Solution<V, T> solution, V selectedVariable) {
205            if (iMPP) {
206                if (selectedVariable.getInitialAssignment() != null) {
207                    if (solution.getModel().nrUnassignedVariables() == 0) {
208                        if (solution.getModel().perturbVariables().size() <= iMPPLimit)
209                            iMPPLimit = solution.getModel().perturbVariables().size() - 1;
210                    }
211                    if (iMPPLimit >= 0 && solution.getModel().perturbVariables().size() > iMPPLimit)
212                        return selectedVariable.getInitialAssignment();
213                    if (selectedVariable.getInitialAssignment() != null && ToolBox.random() <= iInitialSelectionProb)
214                        return selectedVariable.getInitialAssignment();
215                }
216            }
217    
218            List<T> values = selectedVariable.values();
219            if (ToolBox.random() <= iRandomWalkProb)
220                return ToolBox.random(values);
221            if (iProp != null && selectedVariable.getAssignment() == null && ToolBox.random() <= iGoodSelectionProb) {
222                Collection<T> goodValues = iProp.goodValues(selectedVariable);
223                if (!goodValues.isEmpty())
224                    values = new ArrayList<T>(goodValues);
225            }
226            if (values.size() == 1)
227                return values.get(0);
228    
229            List<T> bestValues = null;
230            double bestWeightedSum = 0;
231    
232            for (T value : values) {
233                if (iTabu != null && iTabu.contains(value))
234                    continue;
235                if (selectedVariable.getAssignment() != null && selectedVariable.getAssignment().equals(value))
236                    continue;
237    
238                Collection<T> conf = solution.getModel().conflictValues(value);
239                if (conf.contains(value))
240                    continue;
241    
242                double weightedConflicts = (iStat == null || iWeightWeightedCoflicts == 0.0 ? 0.0 : iStat.countRemovals(
243                        solution.getIteration(), conf, value));
244                double potentialConflicts = (iStat == null || iWeightPotentialConflicts == 0.0 ? 0.0 : iStat
245                        .countPotentialConflicts(solution.getIteration(), value, 3));
246    
247                long deltaInitialAssignments = 0;
248                if (iMPP && iWeightDeltaInitialAssignment != 0.0) {
249                    if (iViolatedInitials != null) {
250                        Set<T> violations = iViolatedInitials.getViolatedInitials(value);
251                        if (violations != null) {
252                            for (T aValue : violations) {
253                                if (aValue.variable().getAssignment() == null
254                                        || aValue.variable().getAssignment().equals(aValue))
255                                    deltaInitialAssignments += 2;
256                            }
257                        }
258                    }
259                    for (Iterator<T> it1 = conf.iterator(); it1.hasNext();) {
260                        T aValue = it1.next();
261                        if (aValue.variable().getInitialAssignment() != null)
262                            deltaInitialAssignments--;
263                    }
264                    if (selectedVariable.getInitialAssignment() != null
265                            && !selectedVariable.getInitialAssignment().equals(value)) {
266                        deltaInitialAssignments++;
267                    }
268                    if (iMPPLimit >= 0
269                            && (solution.getModel().perturbVariables().size() + deltaInitialAssignments) > iMPPLimit)
270                        continue;
271                }
272    
273                double weightedSum = (iWeightDeltaInitialAssignment * deltaInitialAssignments)
274                        + (iWeightPotentialConflicts * potentialConflicts) + (iWeightWeightedCoflicts * weightedConflicts)
275                        + (iWeightCoflicts * conf.size()) + (iWeightNrAssignments * value.countAssignments())
276                        + (iWeightValue * value.toDouble());
277    
278                if (bestValues == null || bestWeightedSum > weightedSum) {
279                    bestWeightedSum = weightedSum;
280                    if (bestValues == null)
281                        bestValues = new ArrayList<T>();
282                    else
283                        bestValues.clear();
284                    bestValues.add(value);
285                } else {
286                    if (bestWeightedSum == weightedSum)
287                        bestValues.add(value);
288                }
289            }
290    
291            T selectedValue = (bestValues == null ? null : ToolBox.random(bestValues));
292            if (selectedValue == null)
293                selectedValue = ToolBox.random(values);
294            if (iTabu != null) {
295                if (iTabu.size() == iTabuPos)
296                    iTabu.add(selectedValue);
297                else
298                    iTabu.set(iTabuPos, selectedValue);
299                iTabuPos = (iTabuPos + 1) % iTabuSize;
300            }
301            return (bestValues == null ? null : selectedValue);
302        }
303    
304    }