net.sf.cpsolver.ifs.heuristics
Class BacktrackNeighbourSelection

java.lang.Object
  net.sf.cpsolver.ifs.heuristics.StandardNeighbourSelection
      net.sf.cpsolver.ifs.heuristics.BacktrackNeighbourSelection

All Implemented Interfaces:

NeighbourSelection

Direct Known Subclasses:

RandomizedBacktrackNeighbourSelection

public class BacktrackNeighbourSelection
extends StandardNeighbourSelection

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.1 (Student Sectioning)
Copyright (C) 2007 Tomáš Müller
muller@unitime.org
Lazenska 391, 76314 Zlin, Czech Republic

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 2.1 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, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

Nested Class Summary

class

BacktrackNeighbourSelection.BackTrackNeighbour Backtracking neighbour

Field Summary

protected BacktrackNeighbourSelection.BackTrackNeighbour	iBackTrackNeighbour
protected Solution	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(Vector variables2resolve, int idx, int depth) Backtracking
protected boolean	canContinue(Vector variables2resolve, int idx, int depth) Check whether backtrack can continue
protected boolean	canContinueEvaluation()
protected boolean	checkBound(Vector variables2resolve, int idx, int depth, Value value, Set 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 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	selectNeighbour(Solution solution) Select neighbour.
Neighbour	selectNeighbour(Solution solution, Variable 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 Enumeration	values(Variable 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 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 solver)

Solver initialization

Specified by:

init in interface NeighbourSelection

Overrides:

init in class StandardNeighbourSelection

selectNeighbour

public Neighbour selectNeighbour(Solution 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

Overrides:

selectNeighbour in class StandardNeighbourSelection

Parameters:

solution - given solution

Returns:

a neighbour assignment

selectNeighbour

public Neighbour selectNeighbour(Solution solution,
                                 Variable 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 Enumeration values(Variable variable)

List of values of the given variable that will be considered

checkBound

protected boolean checkBound(Vector variables2resolve,
                             int idx,
                             int depth,
                             Value value,
                             Set conflicts)

Check bound

canContinue

protected boolean canContinue(Vector variables2resolve,
                              int idx,
                              int depth)

Check whether backtrack can continue

canContinueEvaluation

protected boolean canContinueEvaluation()

backtrack

protected void backtrack(Vector 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