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