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 selectNeighbour(solution, variable, context); 131 return context.getBackTrackNeighbour(); 132 } 133 134 protected void selectNeighbour(Solution<V, T> solution, V variable, BacktrackNeighbourSelectionContext context) { 135 Lock lock = solution.getLock().writeLock(); 136 lock.lock(); 137 try { 138 if (sLog.isDebugEnabled()) 139 sLog.debug("-- before BT (" + variable.getName() + "): nrAssigned=" + solution.getAssignment().nrAssignedVariables() + ", value=" + solution.getModel().getTotalValue(solution.getAssignment())); 140 141 List<V> variables2resolve = new ArrayList<V>(1); 142 variables2resolve.add(variable); 143 backtrack(context, variables2resolve, 0, iDepth); 144 145 if (sLog.isDebugEnabled()) 146 sLog.debug("-- after BT (" + variable.getName() + "): nrAssigned=" + solution.getAssignment().nrAssignedVariables() + ", value=" + solution.getModel().getTotalValue(solution.getAssignment())); 147 } finally { 148 lock.unlock(); 149 } 150 151 if (sLog.isDebugEnabled()) 152 sLog.debug("-- selected neighbour: " + context.getBackTrackNeighbour()); 153 } 154 155 private boolean containsConstantValues(Collection<T> values) { 156 for (T value : values) { 157 if (value.variable() instanceof ConstantVariable && ((ConstantVariable<?>) value.variable()).isConstant()) 158 return true; 159 } 160 return false; 161 } 162 163 /** List of values of the given variable that will be considered 164 * @param context assignment context 165 * @param variable given variable 166 * @return values of the given variable that will be considered 167 **/ 168 protected Iterator<T> values(BacktrackNeighbourSelectionContext context, V variable) { 169 return variable.values(context.getAssignment()).iterator(); 170 } 171 172 /** Check bound 173 * @param variables2resolve unassigned variables that are in conflict with the current solution 174 * @param idx position in variables2resolve 175 * @param depth current depth 176 * @param value value to check 177 * @param conflicts conflicting values 178 * @return bound (best possible improvement) 179 **/ 180 protected boolean checkBound(List<V> variables2resolve, int idx, int depth, T value, Set<T> conflicts) { 181 int nrUnassigned = variables2resolve.size() - idx; 182 if ((nrUnassigned + conflicts.size() > depth)) { 183 if (sLog.isDebugEnabled()) 184 sLog.debug(" -- too deap"); 185 return false; 186 } 187 if (containsConstantValues(conflicts)) { 188 if (sLog.isDebugEnabled()) 189 sLog.debug(" -- contains constants values"); 190 return false; 191 } 192 boolean containAssigned = false; 193 for (Iterator<T> i = conflicts.iterator(); !containAssigned && i.hasNext();) { 194 T conflict = i.next(); 195 int confIdx = variables2resolve.indexOf(conflict.variable()); 196 if (confIdx >= 0 && confIdx <= idx) { 197 if (sLog.isDebugEnabled()) 198 sLog.debug(" -- contains resolved variable " + conflict.variable()); 199 containAssigned = true; 200 } 201 } 202 if (containAssigned) 203 return false; 204 return true; 205 } 206 207 /** Check whether backtrack can continue 208 * @param context assignment context 209 * @param variables2resolve unassigned variables that are in conflict with the current solution 210 * @param idx position in variables2resolve 211 * @param depth current depth 212 * @return true if the search can continue 213 **/ 214 protected boolean canContinue(BacktrackNeighbourSelectionContext context, List<V> variables2resolve, int idx, int depth) { 215 if (depth <= 0) { 216 if (sLog.isDebugEnabled()) 217 sLog.debug(" -- depth reached"); 218 return false; 219 } 220 if (context.isTimeoutReached()) { 221 if (sLog.isDebugEnabled()) 222 sLog.debug(" -- timeout reached"); 223 return false; 224 } 225 if (context.isMaxItersReached()) { 226 if (sLog.isDebugEnabled()) 227 sLog.debug(" -- max number of iterations reached"); 228 return false; 229 } 230 return true; 231 } 232 233 protected boolean canContinueEvaluation(BacktrackNeighbourSelectionContext context) { 234 return !context.isMaxItersReached() && !context.isTimeoutReached(); 235 } 236 237 /** Backtracking 238 * @param context assignment context 239 * @param variables2resolve unassigned variables that are in conflict with the current solution 240 * @param idx position in variables2resolve 241 * @param depth current depth 242 **/ 243 protected void backtrack(BacktrackNeighbourSelectionContext context, List<V> variables2resolve, int idx, int depth) { 244 if (sLog.isDebugEnabled()) 245 sLog.debug(" -- bt[" + depth + "]: " + idx + " of " + variables2resolve.size() + " " + variables2resolve); 246 context.incIteration(); 247 int nrUnassigned = variables2resolve.size() - idx; 248 if (nrUnassigned == 0) { 249 context.saveBest(variables2resolve); 250 return; 251 } 252 if (!canContinue(context, variables2resolve, idx, depth)) 253 return; 254 V variable = variables2resolve.get(idx); 255 if (sLog.isDebugEnabled()) 256 sLog.debug(" -- variable " + variable); 257 for (Iterator<T> e = values(context, variable); canContinueEvaluation(context) && e.hasNext();) { 258 T value = e.next(); 259 T current = context.getAssignment().getValue(variable); 260 if (value.equals(current)) 261 continue; 262 if (sLog.isDebugEnabled()) 263 sLog.debug(" -- value " + value); 264 Set<T> conflicts = context.getModel().conflictValues(context.getAssignment(), value); 265 if (sLog.isDebugEnabled()) 266 sLog.debug(" -- conflicts " + conflicts); 267 if (!checkBound(variables2resolve, idx, depth, value, conflicts)) 268 continue; 269 List<V> newVariables2resolve = new ArrayList<V>(variables2resolve); 270 for (Iterator<T> i = conflicts.iterator(); i.hasNext();) { 271 T conflict = i.next(); 272 context.getAssignment().unassign(0, conflict.variable()); 273 if (!newVariables2resolve.contains(conflict.variable())) 274 newVariables2resolve.add(conflict.variable()); 275 } 276 if (current != null) 277 context.getAssignment().unassign(0, current.variable()); 278 context.getAssignment().assign(0, value); 279 backtrack(context, newVariables2resolve, idx + 1, depth - 1); 280 if (current == null) 281 context.getAssignment().unassign(0, variable); 282 else 283 context.getAssignment().assign(0, current); 284 for (Iterator<T> i = conflicts.iterator(); i.hasNext();) { 285 T conflict = i.next(); 286 context.getAssignment().assign(0, conflict); 287 } 288 } 289 } 290 291 /** Backtracking neighbour */ 292 public class BackTrackNeighbour implements Neighbour<V, T> { 293 private double iTotalValue = 0; 294 private double iValue = 0; 295 private List<T> iDifferentAssignments = null; 296 private Model<V, T> iModel = null; 297 298 /** 299 * Constructor 300 * 301 * @param context assignment context 302 * @param resolvedVariables 303 * variables that has been changed 304 */ 305 public BackTrackNeighbour(BacktrackNeighbourSelectionContext context, List<V> resolvedVariables) { 306 iTotalValue = context.getModel().getTotalValue(context.getAssignment()); 307 iDifferentAssignments = new ArrayList<T>(); 308 for (V variable : resolvedVariables) { 309 T value = variable.getAssignment(context.getAssignment()); 310 iDifferentAssignments.add(value); 311 } 312 iValue = iTotalValue - context.iValue; 313 if (sLog.isDebugEnabled()) 314 iModel = context.getModel(); 315 } 316 317 /** 318 * Constructor 319 * 320 * @param context assignment context 321 * @param resolvedVariables 322 * variables that has been changed 323 */ 324 public BackTrackNeighbour(BacktrackNeighbourSelectionContext context, V... resolvedVariables) { 325 iTotalValue = context.getModel().getTotalValue(context.getAssignment()); 326 iDifferentAssignments = new ArrayList<T>(); 327 for (V variable : resolvedVariables) { 328 T value = variable.getAssignment(context.getAssignment()); 329 iDifferentAssignments.add(value); 330 } 331 iValue = iTotalValue - context.iValue; 332 if (sLog.isDebugEnabled()) 333 iModel = context.getModel(); 334 } 335 336 /** Neighbour value (solution total value if the neighbour is applied). 337 * @return value of the new solution 338 **/ 339 public double getTotalValue() { 340 return iTotalValue; 341 } 342 343 /** 344 * Sum of values of variables from the neighbour that change their 345 * values 346 */ 347 @Override 348 public double value(Assignment<V, T> assignment) { 349 return iValue; 350 } 351 352 /** Neighbour assignments 353 * @return list of assignments in this neighbour 354 **/ 355 public List<T> getAssignments() { 356 return iDifferentAssignments; 357 } 358 359 /** 360 * Assign the neighbour 361 */ 362 @Override 363 public void assign(Assignment<V, T> assignment, long iteration) { 364 if (sLog.isDebugEnabled()) 365 sLog.debug("-- before assignment: nrAssigned=" + assignment.nrAssignedVariables() + ", value=" + iModel.getTotalValue(assignment)); 366 if (sLog.isDebugEnabled()) 367 sLog.debug(" " + this); 368 int idx = 0; 369 for (Iterator<T> e = iDifferentAssignments.iterator(); e.hasNext(); idx++) { 370 T p = e.next(); 371 T o = assignment.getValue(p.variable()); 372 if (o != null) { 373 if (idx > 0 && iStat != null) 374 iStat.variableUnassigned(iteration, o, iDifferentAssignments.get(0)); 375 assignment.unassign(iteration, p.variable()); 376 } 377 } 378 for (T p : iDifferentAssignments) { 379 assignment.assign(iteration, p); 380 } 381 if (sLog.isDebugEnabled()) 382 sLog.debug("-- after assignment: nrAssigned=" + assignment.nrAssignedVariables() + ", value=" + iModel.getTotalValue(assignment)); 383 } 384 385 /** 386 * Compare two neighbours 387 * @param solution current solution 388 * @return comparison 389 */ 390 public int compareTo(Solution<V, T> solution) { 391 return Double.compare(iTotalValue, solution.getModel().getTotalValue(solution.getAssignment())); 392 } 393 394 @Override 395 public String toString() { 396 StringBuffer sb = new StringBuffer("BT{value=" + iTotalValue + ": "); 397 for (Iterator<T> e = iDifferentAssignments.iterator(); e.hasNext();) { 398 T p = e.next(); 399 sb.append("\n " + p.variable().getName() + " " + p.getName() + (e.hasNext() ? "," : "")); 400 } 401 sb.append("}"); 402 return sb.toString(); 403 } 404 405 @Override 406 public Map<V, T> assignments() { 407 Map<V, T> ret = new HashMap<V, T>(); 408 for (T p : iDifferentAssignments) 409 ret.put(p.variable(), p); 410 return ret; 411 } 412 } 413 414 /** Return maximal depth 415 * @return maximal search depth 416 **/ 417 public int getDepth() { 418 return iDepth; 419 } 420 421 /** Set maximal depth 422 * @param depth maximal search depth 423 **/ 424 public void setDepth(int depth) { 425 iDepth = depth; 426 } 427 428 /** Return time limit 429 * @return time limit 430 **/ 431 public int getTimeout() { 432 return iTimeout; 433 } 434 435 /** Set time limit 436 * @param timeout time limit 437 **/ 438 public void setTimeout(int timeout) { 439 iTimeout = timeout; 440 } 441 442 /** Return maximal number of iterations 443 * @return maximal number of iterations 444 **/ 445 public int getMaxIters() { 446 return iMaxIters; 447 } 448 449 /** Set maximal number of iterations 450 * @param maxIters maximal number of iterations 451 **/ 452 public void setMaxIters(int maxIters) { 453 iMaxIters = maxIters; 454 } 455 456 public class BacktrackNeighbourSelectionContext implements AssignmentContext { 457 private long iT0, iT1; 458 private boolean iTimeoutReached = false; 459 private int iMaxIters = -1, iNrIters = 0; 460 protected Solution<V, T> iSolution = null; 461 protected BackTrackNeighbour iBackTrackNeighbour = null; 462 protected double iValue = 0; 463 private int iNrAssigned = 0; 464 private boolean iMaxItersReached = false; 465 466 public BacktrackNeighbourSelectionContext(Solution<V, T> solution) { 467 iSolution = solution; 468 iBackTrackNeighbour = null; 469 iValue = solution.getModel().getTotalValue(iSolution.getAssignment()); 470 iNrAssigned = iSolution.getAssignment().nrAssignedVariables(); 471 iT0 = JProf.currentTimeMillis(); 472 iNrIters = 0; 473 iTimeoutReached = false; 474 iMaxItersReached = false; 475 } 476 477 /** Time needed to find a neighbour (last call of selectNeighbour method) 478 * @return search time 479 **/ 480 public long getTime() { 481 return iT1 - iT0; 482 } 483 484 /** 485 * True, if timeout was reached during the last call of selectNeighbour 486 * method 487 * @return true if the timeout was reached 488 */ 489 public boolean isTimeoutReached() { 490 return iTimeoutReached; 491 } 492 493 /** 494 * True, if the maximum number of iterations was reached by the last call of 495 * selectNeighbour method 496 * @return true if the maximum number of iterations was reached 497 */ 498 public boolean isMaxItersReached() { 499 return iMaxItersReached; 500 } 501 502 public BackTrackNeighbour getBackTrackNeighbour() { return iBackTrackNeighbour; } 503 504 public void incIteration() { 505 iT1 = JProf.currentTimeMillis(); 506 if (!iTimeoutReached && iTimeout > 0 && iT1 - iT0 > iTimeout) 507 iTimeoutReached = true; 508 if (!iMaxItersReached && iMaxIters > 0 && iNrIters++ > iMaxIters) 509 iMaxItersReached = true; 510 } 511 512 public void saveBest(List<V> variables2resolve) { 513 if (sLog.isDebugEnabled()) 514 sLog.debug(" -- all assigned"); 515 if (iSolution.getAssignment().nrAssignedVariables() > iNrAssigned || (iSolution.getAssignment().nrAssignedVariables() == iNrAssigned && iValue > iSolution.getModel().getTotalValue(iSolution.getAssignment()))) { 516 if (sLog.isDebugEnabled()) 517 sLog.debug(" -- better than current"); 518 if (iBackTrackNeighbour == null || iBackTrackNeighbour.compareTo(iSolution) >= 0) { 519 if (sLog.isDebugEnabled()) 520 sLog.debug(" -- better than best"); 521 iBackTrackNeighbour = new BackTrackNeighbour(this, variables2resolve); 522 } 523 } 524 } 525 526 public void saveBest(V... variables2resolve) { 527 if (sLog.isDebugEnabled()) 528 sLog.debug(" -- all assigned"); 529 if (iSolution.getAssignment().nrAssignedVariables() > iNrAssigned || (iSolution.getAssignment().nrAssignedVariables() == iNrAssigned && iValue > iSolution.getModel().getTotalValue(iSolution.getAssignment()))) { 530 if (sLog.isDebugEnabled()) 531 sLog.debug(" -- better than current"); 532 if (iBackTrackNeighbour == null || iBackTrackNeighbour.compareTo(iSolution) >= 0) { 533 if (sLog.isDebugEnabled()) 534 sLog.debug(" -- better than best"); 535 iBackTrackNeighbour = new BackTrackNeighbour(this, variables2resolve); 536 } 537 } 538 } 539 540 public Model<V, T> getModel() { return iSolution.getModel();} 541 542 public Assignment<V, T> getAssignment() { return iSolution.getAssignment(); } 543 } 544}