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.logging.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 = org.apache.logging.log4j.LogManager.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, 331 @SuppressWarnings("unchecked") V... resolvedVariables) { 332 iTotalValue = context.getModel().getTotalValue(context.getAssignment()); 333 iDifferentAssignments = new ArrayList<T>(); 334 for (V variable : resolvedVariables) { 335 T value = variable.getAssignment(context.getAssignment()); 336 iDifferentAssignments.add(value); 337 } 338 iValue = iTotalValue - context.iValue; 339 if (sLog.isDebugEnabled()) 340 iModel = context.getModel(); 341 } 342 343 /** Neighbour value (solution total value if the neighbour is applied). 344 * @return value of the new solution 345 **/ 346 public double getTotalValue() { 347 return iTotalValue; 348 } 349 350 /** 351 * Sum of values of variables from the neighbour that change their 352 * values 353 */ 354 @Override 355 public double value(Assignment<V, T> assignment) { 356 return iValue; 357 } 358 359 /** Neighbour assignments 360 * @return list of assignments in this neighbour 361 **/ 362 public List<T> getAssignments() { 363 return iDifferentAssignments; 364 } 365 366 /** 367 * Assign the neighbour 368 */ 369 @Override 370 public void assign(Assignment<V, T> assignment, long iteration) { 371 if (sLog.isDebugEnabled()) 372 sLog.debug("-- before assignment: nrAssigned=" + assignment.nrAssignedVariables() + ", value=" + iModel.getTotalValue(assignment)); 373 if (sLog.isDebugEnabled()) 374 sLog.debug(" " + this); 375 int idx = 0; 376 for (Iterator<T> e = iDifferentAssignments.iterator(); e.hasNext(); idx++) { 377 T p = e.next(); 378 T o = assignment.getValue(p.variable()); 379 if (o != null) { 380 if (idx > 0 && iStat != null) 381 iStat.variableUnassigned(iteration, o, iDifferentAssignments.get(0)); 382 assignment.unassign(iteration, p.variable()); 383 } 384 } 385 for (T p : iDifferentAssignments) { 386 assignment.assign(iteration, p); 387 } 388 if (sLog.isDebugEnabled()) 389 sLog.debug("-- after assignment: nrAssigned=" + assignment.nrAssignedVariables() + ", value=" + iModel.getTotalValue(assignment)); 390 } 391 392 /** 393 * Compare two neighbours 394 * @param solution current solution 395 * @return comparison 396 */ 397 public int compareTo(Solution<V, T> solution) { 398 return Double.compare(iTotalValue, solution.getModel().getTotalValue(solution.getAssignment())); 399 } 400 401 @Override 402 public String toString() { 403 StringBuffer sb = new StringBuffer("BT{value=" + iTotalValue + ": "); 404 for (Iterator<T> e = iDifferentAssignments.iterator(); e.hasNext();) { 405 T p = e.next(); 406 sb.append("\n " + p.variable().getName() + " " + p.getName() + (e.hasNext() ? "," : "")); 407 } 408 sb.append("}"); 409 return sb.toString(); 410 } 411 412 @Override 413 public Map<V, T> assignments() { 414 Map<V, T> ret = new HashMap<V, T>(); 415 for (T p : iDifferentAssignments) 416 ret.put(p.variable(), p); 417 return ret; 418 } 419 } 420 421 /** Return maximal depth 422 * @return maximal search depth 423 **/ 424 public int getDepth() { 425 return iDepth; 426 } 427 428 /** Set maximal depth 429 * @param depth maximal search depth 430 **/ 431 public void setDepth(int depth) { 432 iDepth = depth; 433 } 434 435 /** Return time limit 436 * @return time limit 437 **/ 438 public int getTimeout() { 439 return iTimeout; 440 } 441 442 /** Set time limit 443 * @param timeout time limit 444 **/ 445 public void setTimeout(int timeout) { 446 iTimeout = timeout; 447 } 448 449 /** Return maximal number of iterations 450 * @return maximal number of iterations 451 **/ 452 public int getMaxIters() { 453 return iMaxIters; 454 } 455 456 /** Set maximal number of iterations 457 * @param maxIters maximal number of iterations 458 **/ 459 public void setMaxIters(int maxIters) { 460 iMaxIters = maxIters; 461 } 462 463 public class BacktrackNeighbourSelectionContext implements AssignmentContext { 464 private long iT0, iT1 = 0; 465 private boolean iTimeoutReached = false; 466 private int iMaxIters = -1, iNrIters = 0; 467 protected Solution<V, T> iSolution = null; 468 protected BackTrackNeighbour iBackTrackNeighbour = null; 469 protected double iValue = 0; 470 private int iNrAssigned = 0; 471 private boolean iMaxItersReached = false; 472 473 public BacktrackNeighbourSelectionContext(Solution<V, T> solution) { 474 iSolution = solution; 475 iBackTrackNeighbour = null; 476 iValue = solution.getModel().getTotalValue(iSolution.getAssignment()); 477 iNrAssigned = iSolution.getAssignment().nrAssignedVariables(); 478 iT0 = JProf.currentTimeMillis(); 479 iNrIters = 0; 480 iTimeoutReached = false; 481 iMaxItersReached = false; 482 } 483 484 /** Time needed to find a neighbour (last call of selectNeighbour method) 485 * @return search time 486 **/ 487 public long getTime() { 488 if (iT1 == 0) return JProf.currentTimeMillis() - iT0; 489 return iT1 - iT0; 490 } 491 492 /** 493 * True, if timeout was reached during the last call of selectNeighbour 494 * method 495 * @return true if the timeout was reached 496 */ 497 public boolean isTimeoutReached() { 498 return iTimeoutReached; 499 } 500 501 /** 502 * True, if the maximum number of iterations was reached by the last call of 503 * selectNeighbour method 504 * @return true if the maximum number of iterations was reached 505 */ 506 public boolean isMaxItersReached() { 507 return iMaxItersReached; 508 } 509 510 public BackTrackNeighbour getBackTrackNeighbour() { return iBackTrackNeighbour; } 511 512 public void incIteration() { 513 iT1 = JProf.currentTimeMillis(); 514 if (!iTimeoutReached && iTimeout > 0 && iT1 - iT0 > iTimeout) 515 iTimeoutReached = true; 516 if (!iMaxItersReached && iMaxIters > 0 && iNrIters++ > iMaxIters) 517 iMaxItersReached = true; 518 } 519 520 public void saveBest(List<V> variables2resolve) { 521 if (sLog.isDebugEnabled()) 522 sLog.debug(" -- all assigned"); 523 if (iSolution.getAssignment().nrAssignedVariables() > iNrAssigned || (iSolution.getAssignment().nrAssignedVariables() == iNrAssigned && iValue > iSolution.getModel().getTotalValue(iSolution.getAssignment()))) { 524 if (sLog.isDebugEnabled()) 525 sLog.debug(" -- better than current"); 526 if (iBackTrackNeighbour == null || iBackTrackNeighbour.compareTo(iSolution) >= 0) { 527 if (sLog.isDebugEnabled()) 528 sLog.debug(" -- better than best"); 529 iBackTrackNeighbour = new BackTrackNeighbour(this, variables2resolve); 530 } 531 } 532 } 533 534 public void saveBest(@SuppressWarnings("unchecked") V... variables2resolve) { 535 if (sLog.isDebugEnabled()) 536 sLog.debug(" -- all assigned"); 537 if (iSolution.getAssignment().nrAssignedVariables() > iNrAssigned || (iSolution.getAssignment().nrAssignedVariables() == iNrAssigned && iValue > iSolution.getModel().getTotalValue(iSolution.getAssignment()))) { 538 if (sLog.isDebugEnabled()) 539 sLog.debug(" -- better than current"); 540 if (iBackTrackNeighbour == null || iBackTrackNeighbour.compareTo(iSolution) >= 0) { 541 if (sLog.isDebugEnabled()) 542 sLog.debug(" -- better than best"); 543 iBackTrackNeighbour = new BackTrackNeighbour(this, variables2resolve); 544 } 545 } 546 } 547 548 public Model<V, T> getModel() { return iSolution.getModel();} 549 550 public Assignment<V, T> getAssignment() { return iSolution.getAssignment(); } 551 } 552}