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}