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 }