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