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 ImmutableVectorminimizer()Get the minimizer (solution) to the minimization problem.doubleminimum()Get the (approximate) minimum found.BBNodesearch(BBNode... initials)Search for a solution that optimizes the objective function from the given starting points.voidsetInitials(BBNode... root)Supply the starting points for the search.Booleanstep()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:MinimizationSolutionGet the (approximate) minimum found.- Specified by:
minimumin interfaceMinimizationSolution<Vector>- Returns:
- the (approximate) minimum found
-
minimizer
public ImmutableVector minimizer()
Description copied from interface:MinimizationSolutionGet the minimizer (solution) to the minimization problem.- Specified by:
minimizerin interfaceMinimizationSolution<Vector>- Returns:
- the minimizer
-
setInitials
public final void setInitials(BBNode... root)
Description copied from interface:IterativeMethodSupply the starting points for the search. This can also initialize the state of the algorithm for a new search.- Specified by:
setInitialsin interfaceIterativeMethod<BBNode>- Parameters:
root- the initial guesses
-
step
public Boolean step() throws Exception
Description copied from interface:IterativeMethodDo the next iteration.- Specified by:
stepin 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:IterativeMethodSearch 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:
searchin interfaceIterativeMethod<BBNode>- Parameters:
initials- the initial guesses- Returns:
- an (approximate) optimizer
- Throws:
Exception- when an error occurs during the search
-
-