001package net.sf.cpsolver.coursett.heuristics;
002
003import java.util.ArrayList;
004import java.util.Collection;
005import java.util.List;
006import java.util.Set;
007
008import net.sf.cpsolver.coursett.criteria.TimetablingCriterion;
009import net.sf.cpsolver.coursett.model.Lecture;
010import net.sf.cpsolver.coursett.model.Placement;
011import net.sf.cpsolver.coursett.model.TimetableModel;
012import net.sf.cpsolver.ifs.criteria.Criterion;
013import net.sf.cpsolver.ifs.extension.Extension;
014import net.sf.cpsolver.ifs.extension.MacPropagation;
015import net.sf.cpsolver.ifs.heuristics.ValueSelection;
016import net.sf.cpsolver.ifs.solution.Solution;
017import net.sf.cpsolver.ifs.solver.Solver;
018import net.sf.cpsolver.ifs.util.DataProperties;
019import net.sf.cpsolver.ifs.util.ToolBox;
020
021/**
022 * Placement (value) selection. <br>
023 * <br>
024 * We have implemented a hierarchical handling of the value selection criteria
025 * (see {@link HeuristicSelector}). <br>
026 * <br>
027 * The value selection heuristics also allow for random selection of a value
028 * with a given probability (random walk, e.g., 2%) and, in the case of MPP, to
029 * select the initial value (if it exists) with a given probability (e.g., 70%). <br>
030 * <br>
031 * Parameters (general):
032 * <table border='1'>
033 * <tr>
034 * <th>Parameter</th>
035 * <th>Type</th>
036 * <th>Comment</th>
037 * </tr>
038 * <tr>
039 * <td>Placement.RandomWalkProb</td>
040 * <td>{@link Double}</td>
041 * <td>Random walk probability</td>
042 * </tr>
043 * <tr>
044 * <td>Placement.GoodSelectionProb</td>
045 * <td>{@link Double}</td>
046 * <td>Good value (not removed from domain) selection probability (MAC related)</td>
047 * </tr>
048 * <tr>
049 * <td>Placement.TabuLength</td>
050 * <td>{@link Integer}</td>
051 * <td>Tabu-list length (-1 means do not use tabu-list)</td>
052 * </tr>
053 * <tr>
054 * <td>Placement.MPP_InitialProb</td>
055 * <td>{@link Double}</td>
056 * <td>MPP initial selection probability</td>
057 * </tr>
058 * <tr>
059 * <td>Placement.MPP_Limit</td>
060 * <td>{@link Integer}</td>
061 * <td>MPP: limit on the number of perturbations (-1 for no limit)</td>
062 * </tr>
063 * <tr>
064 * <td>Placement.MPP_PenaltyLimit</td>
065 * <td>{@link Double}</td>
066 * <td>MPP: limit on the perturbations penalty (-1 for no limit)</td>
067 * </tr>
068 * </table>
069 * <br>
070 * Parameters (for each level of selection):
071 * <table border='1'>
072 * <tr>
073 * <th>Parameter</th>
074 * <th>Type</th>
075 * <th>Comment</th>
076 * </tr>
077 * <tr>
078 * <td>Placement.NrAssignmentsWeight1<br>
079 * Placement.NrAssignmentsWeight2<br>
080 * Placement.NrAssignmentsWeight3</td>
081 * <td>{@link Double}</td>
082 * <td>Number of previous assignments of the value weight</td>
083 * </tr>
084 * <tr>
085 * <td>Placement.NrConflictsWeight1,2,3</td>
086 * <td>{@link Double}</td>
087 * <td>Number of conflicts weight</td>
088 * </tr>
089 * <tr>
090 * <td>Placement.WeightedConflictsWeight1,2,3</td>
091 * <td>{@link Double}</td>
092 * <td>Weighted conflicts weight (Conflict-based Statistics related)</td>
093 * </tr>
094 * <tr>
095 * <td>Placement.NrPotentialConflictsWeight1,2,3</td>
096 * <td>{@link Double}</td>
097 * <td>Number of potential conflicts weight (Conflict-based Statistics related)</td>
098 * </tr>
099 * <tr>
100 * <td>Placement.MPP_DeltaInitialAssignmentWeight1,2,3</td>
101 * <td>{@link Double}</td>
102 * <td>Delta initial assigments weight (MPP, violated initials related)</td>
103 * </tr>
104 * <tr>
105 * <td>Placement.NrHardStudConfsWeight1,2,3</td>
106 * <td>{@link Double}</td>
107 * <td>Hard student conflicts weight (student conflicts between single-section
108 * classes)</td>
109 * </tr>
110 * <tr>
111 * <td>Placement.NrStudConfsWeight1,2,3</td>
112 * <td>{@link Double}</td>
113 * <td>Student conflicts weight</td>
114 * </tr>
115 * <tr>
116 * <td>Placement.TimePreferenceWeight1,2,3</td>
117 * <td>{@link Double}</td>
118 * <td>Time preference weight</td>
119 * </tr>
120 * <tr>
121 * <td>Placement.DeltaTimePreferenceWeight1,2,3</td>
122 * <td>{@link Double}</td>
123 * <td>Time preference delta weight (difference between before and after
124 * assignemnt of the value)</td>
125 * </tr>
126 * <tr>
127 * <td>Placement.ConstrPreferenceWeight1,2,3</td>
128 * <td>{@link Double}</td>
129 * <td>Constraint preference weight</td>
130 * </tr>
131 * <tr>
132 * <td>Placement.RoomPreferenceWeight1,2,3</td>
133 * <td>{@link Double}</td>
134 * <td>Room preference weight</td>
135 * </tr>
136 * <tr>
137 * <td>Placement.UselessSlotsWeight1,2,3</td>
138 * <td>{@link Double}</td>
139 * <td>Useless slot weight</td>
140 * </tr>
141 * <tr>
142 * <td>Placement.TooBigRoomWeight1,2,3</td>
143 * <td>{@link Double}</td>
144 * <td>Too big room weight</td>
145 * </tr>
146 * <tr>
147 * <td>Placement.DistanceInstructorPreferenceWeight1,2,3</td>
148 * <td>{@link Double}</td>
149 * <td>Distance (of the rooms of the back-to-back classes) based instructor
150 * preferences weight</td>
151 * </tr>
152 * <tr>
153 * <td>Placement.DeptSpreadPenaltyWeight1,2,3</td>
154 * <td>{@link Double}</td>
155 * <td>Department spreading: penalty of when a slot over initial allowance is
156 * used</td>
157 * </tr>
158 * <tr>
159 * <td>Placement.ThresholdKoef1,2</td>
160 * <td>{@link Double}</td>
161 * <td>Threshold koeficient of the level</td>
162 * </tr>
163 * </table>
164 * 
165 * @see PlacementSelection
166 * @version CourseTT 1.2 (University Course Timetabling)<br>
167 *          Copyright (C) 2006 - 2010 Tomáš Müller<br>
168 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
169 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
170 * <br>
171 *          This library is free software; you can redistribute it and/or modify
172 *          it under the terms of the GNU Lesser General Public License as
173 *          published by the Free Software Foundation; either version 3 of the
174 *          License, or (at your option) any later version. <br>
175 * <br>
176 *          This library is distributed in the hope that it will be useful, but
177 *          WITHOUT ANY WARRANTY; without even the implied warranty of
178 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
179 *          Lesser General Public License for more details. <br>
180 * <br>
181 *          You should have received a copy of the GNU Lesser General Public
182 *          License along with this library; if not see
183 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
184 */
185
186public class PlacementSelection implements ValueSelection<Lecture, Placement> {
187    static final int NR_LEVELS = 3;
188    private static final double PRECISION = 1.0;
189    private static boolean USE_THRESHOLD = true;
190    private boolean iUseThreshold = USE_THRESHOLD;
191    
192    private double iGoodSelectionProb;
193    public static final String GOOD_SELECTION_PROB = "Placement.GoodSelectionProb";
194    private double iRandomWalkProb;
195    public static final String RW_SELECTION_PROB = "Placement.RandomWalkProb";
196    private double iInitialSelectionProb;
197    public static final String INITIAL_SELECTION_PROB = "Placement.MPP_InitialProb";
198    private int iMPPLimit;
199    public static final String NR_MPP_LIMIT = "Placement.MPP_Limit";
200    private double iMPPPenaltyLimit;
201    public static final String NR_MPP_PENALTY_LIMIT = "Placement.MPP_PenaltyLimit";
202
203    private double[] iThresholdKoef = new double[NR_LEVELS];
204    public static final String NR_THRESHOLD_KOEF = "Placement.ThresholdKoef";
205
206    private int iTabuSize = 0;
207    private ArrayList<Placement> iTabu = null;
208    private int iTabuPos = 0;
209    public static final String TABU_LENGTH = "Placement.TabuLength";
210
211    private MacPropagation<Lecture, Placement> iProp = null;
212
213    private boolean iRW = false;
214    private boolean iMPP = false;
215
216    private boolean iCanUnassingSingleton = false;
217
218    @Override
219    public void init(Solver<Lecture, Placement> solver) {
220        for (Extension<Lecture, Placement> extension : solver.getExtensions()) {
221            if (MacPropagation.class.isInstance(extension))
222                iProp = (MacPropagation<Lecture, Placement>) extension;
223        }
224    }
225
226    public PlacementSelection(DataProperties properties) {
227        iMPP = properties.getPropertyBoolean("General.MPP", false);
228        iRW = properties.getPropertyBoolean("General.RandomWalk", true);
229        iCanUnassingSingleton = properties.getPropertyBoolean("Placement.CanUnassingSingleton", iCanUnassingSingleton);
230        iRandomWalkProb = (iRW ? properties.getPropertyDouble(RW_SELECTION_PROB, 0.00) : 0.0);
231        iGoodSelectionProb = properties.getPropertyDouble(GOOD_SELECTION_PROB, 1.00);
232        iInitialSelectionProb = (iMPP ? properties.getPropertyDouble(INITIAL_SELECTION_PROB, 0.75) : 0.0);
233        iMPPLimit = (iMPP ? properties.getPropertyInt(NR_MPP_LIMIT, -1) : -1);
234        iMPPPenaltyLimit = (iMPP ? properties.getPropertyDouble(NR_MPP_PENALTY_LIMIT, -1.0) : -1.0);
235        iTabuSize = properties.getPropertyInt(TABU_LENGTH, -1);
236        if (iTabuSize > 0)
237            iTabu = new ArrayList<Placement>(iTabuSize);
238        iUseThreshold = properties.getPropertyBoolean("Placement.UseThreshold", USE_THRESHOLD);
239        for (int level = 0; level < NR_LEVELS; level++)
240            iThresholdKoef[level] = (USE_THRESHOLD ? properties.getPropertyDouble(NR_THRESHOLD_KOEF + (level + 1), (level == 0 ? 0.1 : 0.0)) : 0.0);
241    }
242
243    @Override
244    public Placement selectValue(Solution<Lecture, Placement> solution, Lecture var) {
245        if (var == null)
246            return null;
247        Lecture selectedVariable = var;
248
249        TimetableModel model = (TimetableModel) solution.getModel();
250        if (selectedVariable.getInitialAssignment() != null) {
251            if (iMPPLimit >= 0 && model.perturbVariables().size() >= iMPPLimit) {
252                if (!containsItselfSingletonOrCommited(model, model.conflictValues(selectedVariable.getInitialAssignment()), selectedVariable.getInitialAssignment()))
253                    return selectedVariable.getInitialAssignment();
254            } else if (iMPPPenaltyLimit >= 0.0 && solution.getPerturbationsCounter() != null && solution.getPerturbationsCounter().getPerturbationPenalty(model) > iMPPPenaltyLimit) {
255                if (!containsItselfSingletonOrCommited(model, model.conflictValues(selectedVariable.getInitialAssignment()), selectedVariable.getInitialAssignment()))
256                    return selectedVariable.getInitialAssignment();
257            } else if (selectedVariable.getInitialAssignment() != null && ToolBox.random() <= iInitialSelectionProb) {
258                if (!containsItselfSingletonOrCommited(model, model.conflictValues(selectedVariable.getInitialAssignment()), selectedVariable.getInitialAssignment()))
259                    return selectedVariable.getInitialAssignment();
260            }
261        }
262
263        List<Placement> values = selectedVariable.values();
264        if (iRW && ToolBox.random() <= iRandomWalkProb) {
265            for (int i = 0; i < 5; i++) {
266                Placement ret = ToolBox.random(values);
267                if (!containsItselfSingletonOrCommited(model, model.conflictValues(ret), ret))
268                    return ret;
269            }
270        }
271        if (iProp != null && selectedVariable.getAssignment() == null && ToolBox.random() <= iGoodSelectionProb) {
272            Collection<Placement> goodValues = iProp.goodValues(selectedVariable);
273            if (!goodValues.isEmpty())
274                values = new ArrayList<Placement>(goodValues);
275        }
276        if (values.size() == 1) {
277            Placement ret = values.get(0);
278            if (!containsItselfSingletonOrCommited(model, model.conflictValues(ret), ret))
279                return ret;
280        }
281
282        long[] bestCost = new long[NR_LEVELS];
283        List<Placement> selectionValues = null;
284
285        HeuristicSelector<Placement> selector = (iUseThreshold ? new HeuristicSelector<Placement>(iThresholdKoef) : null);
286        for (Placement value : values) {
287            if (iTabu != null && iTabu.contains(value))
288                continue;
289            if (selectedVariable.getAssignment() != null && selectedVariable.getAssignment().equals(value))
290                continue;
291
292            Set<Placement> conflicts = value.variable().getModel().conflictValues(value);
293            
294            if (containsItselfSingletonOrCommited(model, conflicts, value))
295                continue;
296
297            if (iUseThreshold) {
298                Double flt = selector.firstLevelThreshold();
299                double[] costs = new double[NR_LEVELS];
300                for (int level = 0; level < NR_LEVELS; level++) {
301                    costs[level] = getCost(level, value, conflicts);
302                    if (level == 0 && flt != null && costs[0] > flt.doubleValue()) {
303                        break;
304                    }
305                }
306                if (flt != null && costs[0] > flt.doubleValue())
307                    continue;
308                selector.add(costs, value);
309            } else {
310                boolean fail = false;
311                boolean best = false;
312                for (int level = 0; !fail && level < 1; level++) {
313                    double val = getCost(level, value, conflicts);
314                    long cost = Math.round(PRECISION * val);
315                    if (selectionValues != null && !best) {
316                        if (cost > bestCost[level]) {
317                            fail = true;
318                        }
319                        if (cost < bestCost[level]) {
320                            bestCost[level] = cost;
321                            selectionValues.clear();
322                            best = true;
323                        }
324                    } else {
325                        bestCost[level] = cost;
326                    }
327                }
328                if (selectionValues == null)
329                    selectionValues = new ArrayList<Placement>(values.size());
330                if (!fail)
331                    selectionValues.add(value);
332            }
333        }
334        // ToolBox.print("Best "+selectionValues.size()+" locations for variable "+selectedVariable.getId()+" have "+bestConflicts+" conflicts ("+bestRemovals+" weighted) and "+bestStudentConflicts+" ("+bestOriginalStudentConflicts+" * "+bestKoef+" + "+bestPenalty+") preference.");
335        Placement selectedValue = null;
336        if (iUseThreshold) {
337            List<HeuristicSelector<Placement>.Element> selectionElements = selector.selection();
338
339            if (selectedVariable.getInitialAssignment() != null) {
340                for (HeuristicSelector<Placement>.Element element : selectionElements) {
341                    Placement value = element.getObject();
342                    if (value.equals(selectedVariable.getInitialAssignment())) {
343                        selectedValue = value;
344                        break;
345                    }
346                }
347                // &&
348                // selectionValues.contains(selectedVariable.getInitialAssignment()))
349                // return selectedVariable.getInitialAssignment();
350            }
351
352            if (selectedValue == null) {
353                HeuristicSelector<Placement>.Element selection = ToolBox.random(selectionElements);
354                selectedValue = (selection == null ? null : selection.getObject());
355            }
356        } else {
357            if (selectedVariable.getInitialAssignment() != null
358                    && selectionValues.contains(selectedVariable.getInitialAssignment()))
359                return selectedVariable.getInitialAssignment();
360            selectedValue = ToolBox.random(selectionValues);
361        }
362        if (selectedValue != null && iTabu != null) {
363            if (iTabu.size() == iTabuPos)
364                iTabu.add(selectedValue);
365            else
366                iTabu.set(iTabuPos, selectedValue);
367            iTabuPos = (iTabuPos + 1) % iTabuSize;
368        }
369        return selectedValue;
370    }
371
372    public boolean containsItselfSingletonOrCommited(TimetableModel model, Set<Placement> values,
373            Placement selectedValue) {
374        if (values.contains(selectedValue))
375            return true;
376        if (model.hasConstantVariables()) {
377            for (Placement placement : values) {
378                Lecture lecture = placement.variable();
379                if (lecture.isCommitted())
380                    return true;
381                if (!iCanUnassingSingleton && lecture.isSingleton())
382                    return true;
383            }
384            return false;
385        } else {
386            if (iCanUnassingSingleton)
387                return false;
388            for (Placement placement : values) {
389                Lecture lecture = placement.variable();
390                if (lecture.isSingleton())
391                    return true;
392            }
393            return false;
394        }
395    }
396
397    private double getCost(int level, Placement value, Set<Placement> conflicts) {
398        double ret = 0.0;
399        for (Criterion<Lecture, Placement> criterion: value.variable().getModel().getCriteria()) {
400            if (criterion instanceof TimetablingCriterion) {
401                double w = ((TimetablingCriterion)criterion).getPlacementSelectionWeight(level);
402                if (w != 0.0)
403                    ret += w * criterion.getValue(value, conflicts);
404            } else {
405                ret += criterion.getWeightedValue(value, conflicts);
406            }
407        }
408        return ret;
409    }
410    
411}