org.cpsolver.ifs.heuristics

Class BacktrackNeighbourSelection<V extends Variable<V,T>,T extends Value<V,T>>

java.lang.Object

org.cpsolver.ifs.heuristics.StandardNeighbourSelection<V,T>

org.cpsolver.ifs.heuristics.BacktrackNeighbourSelection<V,T>

Type Parameters:

V - Variable

T - Value

All Implemented Interfaces:

NeighbourSelection<V,T>

Direct Known Subclasses:

RandomizedBacktrackNeighbourSelection, ShuffleStudentsSelection.ShuffleBacktrackNeighbourSelection

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:

Related Solver Parameters

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

Version:

StudentSct 1.3 (Student Sectioning)
Copyright (C) 2007 - 2014 Tomáš Müller
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/.

Author:

Tomáš Müller

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	BacktrackNeighbourSelection.BackTrackNeighbour Backtracking neighbour
class	BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext

Field Summary

Fields

Modifier and Type	Field and Description
protected BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext	iContext

Fields inherited from class org.cpsolver.ifs.heuristics.StandardNeighbourSelection

iSolver, sLogger

Constructor Summary

Constructors

Constructor and Description
BacktrackNeighbourSelection(DataProperties properties) Constructor

Method Summary

Modifier and Type	Method and Description
protected void	backtrack(BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext context, List<V> variables2resolve, int idx, int depth) Backtracking
protected boolean	canContinue(BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext context, List<V> variables2resolve, int idx, int depth) Check whether backtrack can continue
protected boolean	canContinueEvaluation(BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext context)
protected boolean	checkBound(List<V> variables2resolve, int idx, int depth, T value, Set<T> conflicts) Check bound
BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext	getContext()
int	getDepth() Return maximal depth
int	getMaxIters() Return maximal number of iterations
int	getTimeout() Return time limit
void	init(Solver<V,T> solver) Solver initialization
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.
protected void	selectNeighbour(Solution<V,T> solution, V variable, BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext context)
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(BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext context, V variable) List of values of the given variable that will be considered

Methods inherited from class org.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

iContext

protected BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext iContext

Constructor Detail

BacktrackNeighbourSelection

public BacktrackNeighbourSelection(DataProperties properties)
                            throws Exception

Constructor

Parameters:

properties - configuration

Throws:

Exception - thrown when initialization fails

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>>

Parameters:

solver - current solver

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).

Parameters:

solution - current solution

variable - selected variable

Returns:

a neighbour, null if not found

selectNeighbour

protected void selectNeighbour(Solution<V,T> solution,
                               V variable,
                               BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext context)

getContext

public BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext getContext()

values

protected Iterator<T> values(BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext context,
                             V variable)

List of values of the given variable that will be considered

Parameters:

context - assignment context

variable - given variable

Returns:

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

Parameters:

variables2resolve - unassigned variables that are in conflict with the current solution

idx - position in variables2resolve

depth - current depth

value - value to check

conflicts - conflicting values

Returns:

bound (best possible improvement)

canContinue

protected boolean canContinue(BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext context,
                              List<V> variables2resolve,
                              int idx,
                              int depth)

Check whether backtrack can continue

Parameters:

context - assignment context

variables2resolve - unassigned variables that are in conflict with the current solution

idx - position in variables2resolve

depth - current depth

Returns:

true if the search can continue

canContinueEvaluation

protected boolean canContinueEvaluation(BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext context)

backtrack

protected void backtrack(BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext context,
                         List<V> variables2resolve,
                         int idx,
                         int depth)

Backtracking

Parameters:

context - assignment context

variables2resolve - unassigned variables that are in conflict with the current solution

idx - position in variables2resolve

depth - current depth

getDepth

public int getDepth()

Return maximal depth

Returns:

maximal search depth

setDepth

public void setDepth(int depth)

Set maximal depth

Parameters:

depth - maximal search depth

getTimeout

public int getTimeout()

Return time limit

Returns:

time limit

setTimeout

public void setTimeout(int timeout)

Set time limit

Parameters:

timeout - time limit

getMaxIters

public int getMaxIters()

Return maximal number of iterations

Returns:

maximal number of iterations

setMaxIters

public void setMaxIters(int maxIters)

Set maximal number of iterations

Parameters:

maxIters - maximal number of iterations