# SuanShu, a Java numerical and statistical library

com.numericalmethod.suanshu.misc.algorithm.bb

## Class BranchAndBound

• All Implemented Interfaces:
IterativeMethod<BBNode>, MinimizationSolution<Vector>

public class BranchAndBound
extends 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.

Wikipedia: Branch and bound
• ### 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

All Methods
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.
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 Boolean step()
throws Exception
Description copied from interface: IterativeMethod
Do the next iteration.
Specified by:
step in interface IterativeMethod<BBNode>
Returns:
Throws:
Exception - when an error occurs during the search
• #### search

public BBNode search(BBNode... initials)
throws 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:
Exception - when an error occurs during the search