orbital.algorithm.template
Class BranchAndBound

java.lang.Object
  orbital.algorithm.template.GeneralSearch
      orbital.algorithm.template.GeneralBoundingSearch
          orbital.algorithm.template.BranchAndBound

All Implemented Interfaces:

java.io.Serializable, AlgorithmicTemplate, EvaluativeAlgorithm, HeuristicAlgorithm

Direct Known Subclasses:

ParallelBranchAndBound

public class BranchAndBound
extends GeneralBoundingSearch
implements HeuristicAlgorithm

Branch-and-bound (B&B).

B&B is complete, optimal, and has a time complexity of O(b^d) and a space complexity of O(b*d).

Author:

André Platzer

See Also:

"Lawler, E.L. and Wood, D.E. Branch-and-bound methods: A survey. Operations Research. 14(4):699-719. 1966.", Serialized Form

Note:

is a basic aspect of bounding the search space by the best known solution. This is automatically satisfied by several other search algorithms.

Nested Class Summary

Nested classes/interfaces inherited from class orbital.algorithm.template.GeneralSearch

GeneralSearch.OptionIterator

Nested classes/interfaces inherited from interface orbital.algorithm.template.HeuristicAlgorithm

HeuristicAlgorithm.Configuration, HeuristicAlgorithm.PatternDatabaseHeuristic

Nested classes/interfaces inherited from interface orbital.algorithm.template.EvaluativeAlgorithm

EvaluativeAlgorithm.EvaluationComparator

Constructor Summary

BranchAndBound(Function heuristic, double maximumUpperBound)
Deprecated. Since Orbital1.1 use BranchAndBound(Function,Real) instead.

BranchAndBound(Function heuristic, Real maximumUpperBound)
Create a new instance of Branch and Bound search.

Method Summary

Function	complexity() O(bd) where b is the branching factor and d the solution depth.
protected java.util.Iterator	createTraversal(GeneralSearchProblem problem) Define a traversal order by creating an iterator for the problem's state space.
Function	getEvaluation() f(n) = g(n) + h(n).
Function	getHeuristic() Get the heuristic function used.
Real	getMaxBound() Get the maximum upper bound for a solution.
boolean	isOptimal() Whether this search algorithm is optimal.
protected java.lang.Object	processSolution(java.lang.Object node) Updates bound to solution cost.
void	setHeuristic(Function heuristic) Set the heuristic function to use.
void	setMaxBound(double maximumUpperBound) Deprecated. Since Orbital1.1 use setMaxBound(Real) instead.
void	setMaxBound(Real maximumUpperBound) Set the maximum upper bound for a solution.
protected java.lang.Object	solveImpl(GeneralSearchProblem problem) Implements the solution policy.
Function	spaceComplexity() O(b*d) where b is the branching factor and d the solution depth.

Methods inherited from class orbital.algorithm.template.GeneralBoundingSearch

getBound, isContinuedWhenFound, isOutOfBounds, search, setBound, setBound, setContinuedWhenFound

Methods inherited from class orbital.algorithm.template.GeneralSearch

getProblem, solve

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface orbital.algorithm.template.AlgorithmicTemplate

solve, spaceComplexity

Constructor Detail

BranchAndBound

public BranchAndBound(Function heuristic,
                      Real maximumUpperBound)

Create a new instance of Branch and Bound search.

Parameters:

heuristic - the heuristic cost function h:S→R embedded in the evaluation function f.

maximumUpperBound - is a sufficiently high upper bound for a solution. If there is no solution below this bound, the search will fail.

See Also:

getEvaluation()

BranchAndBound

public BranchAndBound(Function heuristic,
                      double maximumUpperBound)

Deprecated. Since Orbital1.1 use BranchAndBound(Function,Real) instead.

Method Detail

getMaxBound

public Real getMaxBound()

Get the maximum upper bound for a solution.

setMaxBound

public void setMaxBound(Real maximumUpperBound)

Set the maximum upper bound for a solution.

Parameters:

maximumUpperBound - is a sufficiently high upper bound for a solution. If there is no solution below this bound, the search will fail.

setMaxBound

public void setMaxBound(double maximumUpperBound)

Deprecated. Since Orbital1.1 use setMaxBound(Real) instead.

getHeuristic

public Function getHeuristic()

Description copied from interface: HeuristicAlgorithm

Get the heuristic function used.

Specified by:

getHeuristic in interface HeuristicAlgorithm

Returns:

the heuristic cost function h:S→R estimating h^*.

setHeuristic

public void setHeuristic(Function heuristic)

Description copied from interface: HeuristicAlgorithm

Set the heuristic function to use.

An heuristic cost function h:S→R is estimating the cost to get from a node n to a goal G. For several heuristic algorithms this heuristic function needs to be admissible

h ≤ h^* i.e. h is a lower bound for the effective cost function h^*. Then the pathmax heuristic f(s') := max {f(s), g(s') + h(s')} (for transitions s→s'=t(s,a) with a∈A(s)) is monotonic.

A heuristic cost function h is monotonic :⇔ the f-costs (with h) do not decrease in any path from the initial state ⇔ h obeys the triangular inequality

∀s∈S,a∈A(s) h(s) ≤ h(s') + c(s,a) with s' = t(s,a) i.e. the sum of the costs from A to C and from C to B must not be less than the cost from A to B.

A simple improvement for heuristic functions is using pathmax.

Specified by:

setHeuristic in interface HeuristicAlgorithm

Parameters:

heuristic - the heuristic cost function h:S→R estimating h^*. h will be embedded in the evaluation function f.

See Also:

"Pearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, Reading, Massachusetts. 1984."

getEvaluation

public Function getEvaluation()

f(n) = g(n) + h(n).

Specified by:

getEvaluation in interface EvaluativeAlgorithm

Specified by:

getEvaluation in interface HeuristicAlgorithm

Returns:

the evaluation function f:S→R used to evaluate (either utility or cost) value of states.

complexity

public Function complexity()

O(b^d) where b is the branching factor and d the solution depth.

Specified by:

complexity in interface AlgorithmicTemplate

Returns:

the function f for which the solve() method of this algorithm runs in O(f(n)) assuming the algorithmic problem hook to run in O(1).

See Also:

AlgorithmicTemplate.solve(AlgorithmicProblem)

isOptimal

public boolean isOptimal()

Description copied from class: GeneralSearch

Whether this search algorithm is optimal.

If a search algorithm is not optimal, i.e. it might be content with solutions that are sub optimal only, then it can at most reliably find solutions, not best solutions. However, those solutions found still provide an upper bound to the optimal solution.

Specified by:

isOptimal in class GeneralSearch

Returns:

whether this search algorithm is optimal, i.e. whether solutions found are guaranteed to be optimal.

processSolution

protected java.lang.Object processSolution(java.lang.Object node)

Updates bound to solution cost. Since better solutions can only be found below this bound.

Overrides:

processSolution in class GeneralBoundingSearch

Parameters:

node - the node describing the solution.

Returns:

the solution after processing it.

See Also:

Template Method

solveImpl

protected java.lang.Object solveImpl(GeneralSearchProblem problem)

Description copied from class: GeneralSearch

Implements the solution policy.

Like the default solution policies, this implementation will

1. Fetch a traversal order policy by calling GeneralSearch.createTraversal(GeneralSearchProblem).
2. Then call GeneralSearch.search(Iterator) to search through the state space in the traversal order.

However, sophisticated search algorithms may want to change that policy and iterate the above process, resulting in a sequence of calls to those methods. They may do so by by overwriting this method.

Overrides:

solveImpl in class GeneralSearch

Returns:

the solution found by GeneralSearch.search(Iterator).

See Also:

GeneralSearch.search(Iterator)

spaceComplexity

public Function spaceComplexity()

O(b*d) where b is the branching factor and d the solution depth.

Returns:

the function f for which the solve() method of this algorithm consumes memory with an amount in O(f(n)) assuming the algorithmic problem hook uses space in O(1).

See Also:

AlgorithmicTemplate.solve(AlgorithmicProblem)

createTraversal

protected java.util.Iterator createTraversal(GeneralSearchProblem problem)

Description copied from class: GeneralSearch

Define a traversal order by creating an iterator for the problem's state space.

Lays a linear order through the state space which the search can simply follow sequentially. Thus a traversal policy effectively reduces a search problem through a graph to a search problem through a linear sequence of states. Of course, the mere notion of a traversal policy does not yet solve the task of finding a good order of states, but only encapsulate it. Complete search algorithms result from traversal policies that have a linear sequence through the whole state space.

Specified by:

createTraversal in class GeneralSearch

Parameters:

problem - the problem whose state space to create a traversal iterator for.

Returns:

an iterator over the options of the problem's state space thereby encapsulating and hiding the traversal order.

See Also:

Factory Method, GeneralSearch.OptionIterator