Package dev.nm.misc.algorithm.bb
Class BranchAndBound
- java.lang.Object
-
- dev.nm.misc.algorithm.bb.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.- See Also:
- Wikipedia: Branch and bound
-
-
Constructor Summary
Constructors Constructor 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 Instance Methods Concrete Methods Modifier and Type Method 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.
-
-
-
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-searchroot
- 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 interfaceMinimizationSolution<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 interfaceMinimizationSolution<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 interfaceIterativeMethod<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 interfaceIterativeMethod<BBNode>
- Returns:
- the information about this step
- 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 iterativelyIterativeMethod.step()
. It implements a default convergence criterion.- Specified by:
search
in interfaceIterativeMethod<BBNode>
- Parameters:
initials
- the initial guesses- Returns:
- an (approximate) optimizer
- Throws:
Exception
- when an error occurs during the search
-
-