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