net.sf.cpsolver.ifs.heuristics
Class BacktrackNeighbourSelection<V extends Variable<V,T>,T extends Value<V,T>>

java.lang.Object
  extended by net.sf.cpsolver.ifs.heuristics.StandardNeighbourSelection<V,T>
      extended by net.sf.cpsolver.ifs.heuristics.BacktrackNeighbourSelection<V,T>
All Implemented Interfaces:
NeighbourSelection<V,T>
Direct Known Subclasses:
RandomizedBacktrackNeighbourSelection

public class BacktrackNeighbourSelection<V extends Variable<V,T>,T extends Value<V,T>>
extends StandardNeighbourSelection<V,T>

Backtracking-based neighbour selection. A best neighbour that is found by a backtracking-based algorithm within a limited depth from a selected variable is returned.

Parameters:

Parameter Type Comment
Neighbour.BackTrackTimeout Integer Timeout for each neighbour selection (in milliseconds).
Neighbour.BackTrackDepth Integer Limit of search depth.


Version:
StudentSct 1.2 (Student Sectioning)
Copyright (C) 2007 - 2010 Tomas Muller
muller@unitime.org
http://muller.unitime.org

This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library; if not see http://www.gnu.org/licenses/.

Nested Class Summary
 class BacktrackNeighbourSelection.BackTrackNeighbour
          Backtracking neighbour
 
Field Summary
protected  BacktrackNeighbourSelection.BackTrackNeighbour iBackTrackNeighbour
           
protected  Solution<V,T> iSolution
           
protected  double iValue
           
 
Fields inherited from class net.sf.cpsolver.ifs.heuristics.StandardNeighbourSelection
sLogger
 
Constructor Summary
BacktrackNeighbourSelection(DataProperties properties)
          Constructor
 
Method Summary
protected  void backtrack(List<V> variables2resolve, int idx, int depth)
          Backtracking
protected  boolean canContinue(List<V> variables2resolve, int idx, int depth)
          Check whether backtrack can continue
protected  boolean canContinueEvaluation()
           
protected  boolean checkBound(List<V> variables2resolve, int idx, int depth, T value, Set<T> conflicts)
          Check bound
 int getDepth()
          Return maximal depth
 int getMaxIters()
          Return maximal number of iterations
 long getTime()
          Time needed to find a neighbour (last call of selectNeighbour method)
 int getTimeout()
          Return time limit
 void init(Solver<V,T> solver)
          Solver initialization
 boolean isMaxItersReached()
          True, if the maximum number of iterations was reached by the last call of selectNeighbour method
 boolean isTimeoutReached()
          True, if timeout was reached during the last call of selectNeighbour method
 Neighbour<V,T> selectNeighbour(Solution<V,T> solution)
          Select neighbour.
 Neighbour<V,T> selectNeighbour(Solution<V,T> solution, V variable)
          Select neighbour -- starts from the provided variable.
 void setDepth(int depth)
          Set maximal depth
 void setMaxIters(int maxIters)
          Set maximal number of iterations
 void setTimeout(int timeout)
          Set time limit
protected  Iterator<T> values(V variable)
          List of values of the given variable that will be considered
 
Methods inherited from class net.sf.cpsolver.ifs.heuristics.StandardNeighbourSelection
getValueSelection, getVariableSelection, selectValue, selectVariable, setValueSelection, setVariableSelection
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

iSolution

protected Solution<V extends Variable<V,T>,T extends Value<V,T>> iSolution

iBackTrackNeighbour

protected BacktrackNeighbourSelection.BackTrackNeighbour iBackTrackNeighbour

iValue

protected double iValue
Constructor Detail

BacktrackNeighbourSelection

public BacktrackNeighbourSelection(DataProperties properties)
                            throws Exception
Constructor

Parameters:
properties - configuration
Throws:
Exception
Method Detail

init

public void init(Solver<V,T> solver)
Solver initialization

Specified by:
init in interface NeighbourSelection<V extends Variable<V,T>,T extends Value<V,T>>
Overrides:
init in class StandardNeighbourSelection<V extends Variable<V,T>,T extends Value<V,T>>

selectNeighbour

public Neighbour<V,T> selectNeighbour(Solution<V,T> solution)
Select neighbour. The standard variable selection (see StandardNeighbourSelection.getVariableSelection()) is used to select a variable. A backtracking of a limited depth is than employed from this variable. The best assignment found is returned (see BacktrackNeighbourSelection.BackTrackNeighbour).

Specified by:
selectNeighbour in interface NeighbourSelection<V extends Variable<V,T>,T extends Value<V,T>>
Overrides:
selectNeighbour in class StandardNeighbourSelection<V extends Variable<V,T>,T extends Value<V,T>>
Parameters:
solution - given solution
Returns:
a neighbour assignment

selectNeighbour

public Neighbour<V,T> selectNeighbour(Solution<V,T> solution,
                                      V variable)
Select neighbour -- starts from the provided variable. A backtracking of a limited depth is employed from the given variable. The best assignment found is returned (see BacktrackNeighbourSelection.BackTrackNeighbour).


getTime

public long getTime()
Time needed to find a neighbour (last call of selectNeighbour method)


isTimeoutReached

public boolean isTimeoutReached()
True, if timeout was reached during the last call of selectNeighbour method


isMaxItersReached

public boolean isMaxItersReached()
True, if the maximum number of iterations was reached by the last call of selectNeighbour method


values

protected Iterator<T> values(V variable)
List of values of the given variable that will be considered


checkBound

protected boolean checkBound(List<V> variables2resolve,
                             int idx,
                             int depth,
                             T value,
                             Set<T> conflicts)
Check bound


canContinue

protected boolean canContinue(List<V> variables2resolve,
                              int idx,
                              int depth)
Check whether backtrack can continue


canContinueEvaluation

protected boolean canContinueEvaluation()

backtrack

protected void backtrack(List<V> variables2resolve,
                         int idx,
                         int depth)
Backtracking


getDepth

public int getDepth()
Return maximal depth


setDepth

public void setDepth(int depth)
Set maximal depth


getTimeout

public int getTimeout()
Return time limit


setTimeout

public void setTimeout(int timeout)
Set time limit


getMaxIters

public int getMaxIters()
Return maximal number of iterations


setMaxIters

public void setMaxIters(int maxIters)
Set maximal number of iterations



Copyright © 2014 UniTime LLC. All Rights Reserved.