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.

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