001package net.sf.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 net.sf.cpsolver.ifs.constant.ConstantVariable; 010import net.sf.cpsolver.ifs.extension.ConflictStatistics; 011import net.sf.cpsolver.ifs.extension.Extension; 012import net.sf.cpsolver.ifs.model.Neighbour; 013import net.sf.cpsolver.ifs.model.Value; 014import net.sf.cpsolver.ifs.model.Variable; 015import net.sf.cpsolver.ifs.solution.Solution; 016import net.sf.cpsolver.ifs.solver.Solver; 017import net.sf.cpsolver.ifs.util.DataProperties; 018import net.sf.cpsolver.ifs.util.JProf; 019 020import org.apache.log4j.Logger; 021 022/** 023 * Backtracking-based neighbour selection. A best neighbour that is found by a 024 * backtracking-based algorithm within a limited depth from a selected variable 025 * is returned. <br> 026 * <br> 027 * Parameters: <br> 028 * <table border='1'> 029 * <tr> 030 * <th>Parameter</th> 031 * <th>Type</th> 032 * <th>Comment</th> 033 * </tr> 034 * <tr> 035 * <td>Neighbour.BackTrackTimeout</td> 036 * <td>{@link Integer}</td> 037 * <td>Timeout for each neighbour selection (in milliseconds).</td> 038 * </tr> 039 * <tr> 040 * <td>Neighbour.BackTrackDepth</td> 041 * <td>{@link Integer}</td> 042 * <td>Limit of search depth.</td> 043 * </tr> 044 * </table> 045 * 046 * <br> 047 * <br> 048 * 049 * @version StudentSct 1.2 (Student Sectioning)<br> 050 * Copyright (C) 2007 - 2010 Tomáš Müller<br> 051 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 052 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 053 * <br> 054 * This library is free software; you can redistribute it and/or modify 055 * it under the terms of the GNU Lesser General Public License as 056 * published by the Free Software Foundation; either version 3 of the 057 * License, or (at your option) any later version. <br> 058 * <br> 059 * This library is distributed in the hope that it will be useful, but 060 * WITHOUT ANY WARRANTY; without even the implied warranty of 061 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 062 * Lesser General Public License for more details. <br> 063 * <br> 064 * You should have received a copy of the GNU Lesser General Public 065 * License along with this library; if not see 066 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 067 */ 068 069public class BacktrackNeighbourSelection<V extends Variable<V, T>, T extends Value<V, T>> extends 070 StandardNeighbourSelection<V, T> { 071 private ConflictStatistics<V, T> iStat = null; 072 private static Logger sLog = Logger.getLogger(BacktrackNeighbourSelection.class); 073 private int iTimeout = 5000; 074 private int iDepth = 4; 075 076 protected Solution<V, T> iSolution = null; 077 protected BackTrackNeighbour iBackTrackNeighbour = null; 078 protected double iValue = 0; 079 private int iNrAssigned = 0; 080 private long iT0, iT1; 081 private boolean iTimeoutReached = false; 082 private int iMaxIters = -1, iNrIters = 0; 083 private boolean iMaxItersReached = false; 084 085 /** 086 * Constructor 087 * 088 * @param properties 089 * configuration 090 * @throws Exception 091 */ 092 public BacktrackNeighbourSelection(DataProperties properties) throws Exception { 093 super(properties); 094 iTimeout = properties.getPropertyInt("Neighbour.BackTrackTimeout", iTimeout); 095 iDepth = properties.getPropertyInt("Neighbour.BackTrackDepth", iDepth); 096 iMaxIters = properties.getPropertyInt("Neighbour.BackTrackMaxIters", iMaxIters); 097 } 098 099 /** Solver initialization */ 100 @Override 101 public void init(Solver<V, T> solver) { 102 super.init(solver); 103 for (Extension<V, T> extension : solver.getExtensions()) { 104 if (ConflictStatistics.class.isInstance(extension)) 105 iStat = (ConflictStatistics<V, T>) extension; 106 } 107 } 108 109 /** 110 * Select neighbour. The standard variable selection (see 111 * {@link StandardNeighbourSelection#getVariableSelection()}) is used to 112 * select a variable. A backtracking of a limited depth is than employed 113 * from this variable. The best assignment found is returned (see 114 * {@link BackTrackNeighbour}). 115 **/ 116 @Override 117 public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) { 118 return selectNeighbour(solution, getVariableSelection().selectVariable(solution)); 119 } 120 121 /** 122 * Select neighbour -- starts from the provided variable. A backtracking of 123 * a limited depth is employed from the given variable. The best assignment 124 * found is returned (see {@link BackTrackNeighbour}). 125 **/ 126 public synchronized Neighbour<V, T> selectNeighbour(Solution<V, T> solution, V variable) { 127 if (variable == null) 128 return null; 129 130 iSolution = solution; 131 iBackTrackNeighbour = null; 132 iValue = solution.getModel().getTotalValue(); 133 iNrAssigned = solution.getModel().assignedVariables().size(); 134 iT0 = JProf.currentTimeMillis(); 135 iNrIters = 0; 136 iTimeoutReached = false; 137 iMaxItersReached = false; 138 139 synchronized (solution) { 140 if (sLog.isDebugEnabled()) 141 sLog.debug("-- before BT (" + variable.getName() + "): nrAssigned=" 142 + iSolution.getModel().assignedVariables().size() + ", value=" 143 + iSolution.getModel().getTotalValue()); 144 145 List<V> variables2resolve = new ArrayList<V>(1); 146 variables2resolve.add(variable); 147 backtrack(variables2resolve, 0, iDepth); 148 149 if (sLog.isDebugEnabled()) 150 sLog.debug("-- after BT (" + variable.getName() + "): nrAssigned=" 151 + iSolution.getModel().assignedVariables().size() + ", value=" 152 + iSolution.getModel().getTotalValue()); 153 } 154 155 iT1 = JProf.currentTimeMillis(); 156 157 if (sLog.isDebugEnabled()) 158 sLog.debug("-- selected neighbour: " + iBackTrackNeighbour); 159 return iBackTrackNeighbour; 160 } 161 162 /** Time needed to find a neighbour (last call of selectNeighbour method) */ 163 public long getTime() { 164 return iT1 - iT0; 165 } 166 167 /** 168 * True, if timeout was reached during the last call of selectNeighbour 169 * method 170 */ 171 public boolean isTimeoutReached() { 172 return iTimeoutReached; 173 } 174 175 /** 176 * True, if the maximum number of iterations was reached by the last call of 177 * selectNeighbour method 178 */ 179 public boolean isMaxItersReached() { 180 return iMaxItersReached; 181 } 182 183 private boolean containsConstantValues(Collection<T> values) { 184 for (T value : values) { 185 if (value.variable() instanceof ConstantVariable && ((ConstantVariable) value.variable()).isConstant()) 186 return true; 187 } 188 return false; 189 } 190 191 /** List of values of the given variable that will be considered */ 192 protected Iterator<T> values(V variable) { 193 return variable.values().iterator(); 194 } 195 196 /** Check bound */ 197 protected boolean checkBound(List<V> variables2resolve, int idx, int depth, T value, Set<T> conflicts) { 198 int nrUnassigned = variables2resolve.size() - idx; 199 if ((nrUnassigned + conflicts.size() > depth)) { 200 if (sLog.isDebugEnabled()) 201 sLog.debug(" -- too deap"); 202 return false; 203 } 204 if (containsConstantValues(conflicts)) { 205 if (sLog.isDebugEnabled()) 206 sLog.debug(" -- contains constants values"); 207 return false; 208 } 209 boolean containAssigned = false; 210 for (Iterator<T> i = conflicts.iterator(); !containAssigned && i.hasNext();) { 211 T conflict = i.next(); 212 int confIdx = variables2resolve.indexOf(conflict.variable()); 213 if (confIdx >= 0 && confIdx <= idx) { 214 if (sLog.isDebugEnabled()) 215 sLog.debug(" -- contains resolved variable " + conflict.variable()); 216 containAssigned = true; 217 } 218 } 219 if (containAssigned) 220 return false; 221 return true; 222 } 223 224 /** Check whether backtrack can continue */ 225 protected boolean canContinue(List<V> variables2resolve, int idx, int depth) { 226 if (depth <= 0) { 227 if (sLog.isDebugEnabled()) 228 sLog.debug(" -- depth reached"); 229 return false; 230 } 231 if (iTimeoutReached) { 232 if (sLog.isDebugEnabled()) 233 sLog.debug(" -- timeout reached"); 234 return false; 235 } 236 if (iMaxItersReached) { 237 if (sLog.isDebugEnabled()) 238 sLog.debug(" -- max number of iterations reached"); 239 return false; 240 } 241 return true; 242 } 243 244 protected boolean canContinueEvaluation() { 245 return !iTimeoutReached && !iMaxItersReached; 246 } 247 248 /** Backtracking */ 249 protected void backtrack(List<V> variables2resolve, int idx, int depth) { 250 if (sLog.isDebugEnabled()) 251 sLog.debug(" -- bt[" + depth + "]: " + idx + " of " + variables2resolve.size() + " " + variables2resolve); 252 if (!iTimeoutReached && iTimeout > 0 && JProf.currentTimeMillis() - iT0 > iTimeout) 253 iTimeoutReached = true; 254 if (!iMaxItersReached && iMaxIters > 0 && iNrIters++ > iMaxIters) 255 iMaxItersReached = true; 256 int nrUnassigned = variables2resolve.size() - idx; 257 if (nrUnassigned == 0) { 258 if (sLog.isDebugEnabled()) 259 sLog.debug(" -- all assigned"); 260 if (iSolution.getModel().assignedVariables().size() > iNrAssigned 261 || (iSolution.getModel().assignedVariables().size() == iNrAssigned && iValue > iSolution.getModel() 262 .getTotalValue())) { 263 if (sLog.isDebugEnabled()) 264 sLog.debug(" -- better than current"); 265 if (iBackTrackNeighbour == null || iBackTrackNeighbour.compareTo(iSolution) >= 0) { 266 if (sLog.isDebugEnabled()) 267 sLog.debug(" -- better than best"); 268 iBackTrackNeighbour = new BackTrackNeighbour(variables2resolve); 269 } 270 } 271 return; 272 } 273 if (!canContinue(variables2resolve, idx, depth)) 274 return; 275 V variable = variables2resolve.get(idx); 276 if (sLog.isDebugEnabled()) 277 sLog.debug(" -- variable " + variable); 278 for (Iterator<T> e = values(variable); canContinueEvaluation() && e.hasNext();) { 279 T value = e.next(); 280 if (value.equals(variable.getAssignment())) 281 continue; 282 if (sLog.isDebugEnabled()) 283 sLog.debug(" -- value " + value); 284 Set<T> conflicts = iSolution.getModel().conflictValues(value); 285 if (sLog.isDebugEnabled()) 286 sLog.debug(" -- conflicts " + conflicts); 287 if (!checkBound(variables2resolve, idx, depth, value, conflicts)) 288 continue; 289 T current = variable.getAssignment(); 290 List<V> newVariables2resolve = new ArrayList<V>(variables2resolve); 291 for (Iterator<T> i = conflicts.iterator(); i.hasNext();) { 292 T conflict = i.next(); 293 conflict.variable().unassign(0); 294 if (!newVariables2resolve.contains(conflict.variable())) 295 newVariables2resolve.add(conflict.variable()); 296 } 297 if (current != null) 298 current.variable().unassign(0); 299 value.variable().assign(0, value); 300 backtrack(newVariables2resolve, idx + 1, depth - 1); 301 if (current == null) 302 variable.unassign(0); 303 else 304 variable.assign(0, current); 305 for (Iterator<T> i = conflicts.iterator(); i.hasNext();) { 306 T conflict = i.next(); 307 conflict.variable().assign(0, conflict); 308 } 309 } 310 } 311 312 /** Backtracking neighbour */ 313 public class BackTrackNeighbour extends Neighbour<V, T> { 314 private double iTotalValue = 0; 315 private double iValue = 0; 316 private List<T> iDifferentAssignments = null; 317 318 /** 319 * Constructor 320 * 321 * @param resolvedVariables 322 * variables that has been changed 323 */ 324 public BackTrackNeighbour(List<V> resolvedVariables) { 325 iTotalValue = iSolution.getModel().getTotalValue(); 326 iValue = 0; 327 iDifferentAssignments = new ArrayList<T>(); 328 for (V variable : resolvedVariables) { 329 T value = variable.getAssignment(); 330 iDifferentAssignments.add(value); 331 iValue += value.toDouble(); 332 } 333 } 334 335 /** Neighbour value (solution total value if the neighbour is applied). */ 336 public double getTotalValue() { 337 return iTotalValue; 338 } 339 340 /** 341 * Sum of values of variables from the neighbour that change their 342 * values 343 */ 344 @Override 345 public double value() { 346 return iValue; 347 } 348 349 /** Neighbour assignments */ 350 public List<T> getAssignments() { 351 return iDifferentAssignments; 352 } 353 354 /** 355 * Assign the neighbour 356 */ 357 @Override 358 public void assign(long iteration) { 359 if (sLog.isDebugEnabled()) 360 sLog.debug("-- before assignment: nrAssigned=" + iSolution.getModel().assignedVariables().size() 361 + ", value=" + iSolution.getModel().getTotalValue()); 362 if (sLog.isDebugEnabled()) 363 sLog.debug(" " + this); 364 int idx = 0; 365 for (Iterator<T> e = iDifferentAssignments.iterator(); e.hasNext(); idx++) { 366 T p = e.next(); 367 if (p.variable().getAssignment() != null) { 368 if (idx > 0 && iStat != null) 369 iStat.variableUnassigned(iteration, p.variable().getAssignment(), iDifferentAssignments.get(0)); 370 p.variable().unassign(iteration); 371 } 372 } 373 for (T p : iDifferentAssignments) { 374 p.variable().assign(iteration, p); 375 } 376 if (sLog.isDebugEnabled()) 377 sLog.debug("-- after assignment: nrAssigned=" + iSolution.getModel().assignedVariables().size() 378 + ", value=" + iSolution.getModel().getTotalValue()); 379 } 380 381 /** 382 * Compare two neighbours 383 */ 384 public int compareTo(Solution<V, T> solution) { 385 return Double.compare(iTotalValue, solution.getModel().getTotalValue()); 386 } 387 388 @Override 389 public String toString() { 390 StringBuffer sb = new StringBuffer("BT{value=" + (iTotalValue - iSolution.getModel().getTotalValue()) 391 + ": "); 392 for (Iterator<T> e = iDifferentAssignments.iterator(); e.hasNext();) { 393 T p = e.next(); 394 sb.append("\n " + p.variable().getName() + " " + p.getName() + (e.hasNext() ? "," : "")); 395 } 396 sb.append("}"); 397 return sb.toString(); 398 } 399 } 400 401 /** Return maximal depth */ 402 public int getDepth() { 403 return iDepth; 404 } 405 406 /** Set maximal depth */ 407 public void setDepth(int depth) { 408 iDepth = depth; 409 } 410 411 /** Return time limit */ 412 public int getTimeout() { 413 return iTimeout; 414 } 415 416 /** Set time limit */ 417 public void setTimeout(int timeout) { 418 iTimeout = timeout; 419 } 420 421 /** Return maximal number of iterations */ 422 public int getMaxIters() { 423 return iMaxIters; 424 } 425 426 /** Set maximal number of iterations */ 427 public void setMaxIters(int maxIters) { 428 iMaxIters = maxIters; 429 } 430}