Module branch_and_bound 

Branch-and-Bound algorithm for Mixed-Integer Programming

The branch-and-bound algorithm systematically explores the space of integer solutions by:

1. Solving LP relaxations at each node
2. Branching on a fractional integer variable
3. Using bounds to prune subproblems that cannot improve on the incumbent

Algorithm

• Start with the LP relaxation of the full problem
• Maintain an incumbent (best integer solution found)
• Branch by adding floor/ceil constraints on a fractional variable
• Prune nodes where LP lower bound >= incumbent objective

References

• Land, A.H. & Doig, A.G. (1960). “An automatic method of solving discrete programming problems.” Econometrica, 28(3), 497-520.

Structs

BranchAndBoundOptions

Options for branch-and-bound

BranchAndBoundSolver

Branch-and-bound solver for mixed-integer programming

Enums

NodeSelection

Node selection strategy for branch-and-bound

VariableSelection

Variable selection strategy for branching