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