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