com.numericalmethod.suanshu.algorithm.bb

Class BranchAndBound

java.lang.Object

com.numericalmethod.suanshu.algorithm.bb.BranchAndBound

All Implemented Interfaces:

IterativeMethod<BBNode>, MinimizationSolution<Vector>, java.io.Serializable

public class BranchAndBound
extends java.lang.Object
implements MinimizationSolution<Vector>, IterativeMethod<BBNode>

Branch-and-Bound (BB or B&B) is a general algorithm for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization. It consists of a systematic enumeration of all candidate solutions, where large subsets of fruitless candidates are discarded en masse, by using upper and lower estimated bounds of the quantity being optimized.

This implementation is solving a minimization problem.

See Also:

Wikipedia: Branch and bound, Serialized Form

Constructor Summary

Constructors

Constructor and Description
BranchAndBound(ActiveList activeList, BBNode root) Solve a minimization problem using a branch-and-bound algorithm.
BranchAndBound(BBNode root) Solve a minimization problem using a branch-and-bound algorithm using depth-first search.

Method Summary

Modifier and Type	Method and Description
ImmutableVector	minimizer() Get the minimizer (solution) to the minimization problem.
double	minimum() Get the (approximate) minimum found.
BBNode	search(BBNode... initials) Search for a solution that optimizes the objective function from the given starting points.
void	setInitials(BBNode... root) Supply the starting points for the search.
java.lang.Boolean	step() Do the next iteration.

Methods inherited from class java.lang.Object

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

Constructor Detail

BranchAndBound

public BranchAndBound(ActiveList activeList,
                      BBNode root)

Solve a minimization problem using a branch-and-bound algorithm.

Parameters:

activeList - the node popping strategy, e.g., depth-first-search, best-first-search

root - the root node of a minimization problem

BranchAndBound

public BranchAndBound(BBNode root)

Solve a minimization problem using a branch-and-bound algorithm using depth-first search.

Parameters:

root - the root node of a minimization problem

Method Detail

minimum

public double minimum()

Description copied from interface: MinimizationSolution

Get the (approximate) minimum found.

Specified by:

minimum in interface MinimizationSolution<Vector>

Returns:

the (approximate) minimum found

minimizer

public ImmutableVector minimizer()

Description copied from interface: MinimizationSolution

Get the minimizer (solution) to the minimization problem.

Specified by:

minimizer in interface MinimizationSolution<Vector>

Returns:

the minimizer

setInitials

public final void setInitials(BBNode... root)

Description copied from interface: IterativeMethod

Supply the starting points for the search. This can also initialize the state of the algorithm for a new search.

Specified by:

setInitials in interface IterativeMethod<BBNode>

Parameters:

root - the initial guesses

step

public java.lang.Boolean step()
                       throws java.lang.Exception

Description copied from interface: IterativeMethod

Do the next iteration.

Specified by:

step in interface IterativeMethod<BBNode>

Returns:

the information about this step

Throws:

java.lang.Exception - when an error occurs during the search

search

public BBNode search(BBNode... initials)
              throws java.lang.Exception

Description copied from interface: IterativeMethod

Search for a solution that optimizes the objective function from the given starting points. This method typically calls first #setInitials(S[]) and then iteratively IterativeMethod.step(). It implements a default convergence criterion.

Specified by:

search in interface IterativeMethod<BBNode>

Parameters:

initials - the initial guesses

Returns:

an (approximate) optimizer

Throws:

java.lang.Exception - when an error occurs during the search