BranchAndBoundSolver<T>
Models & Types · AiDotNet.Solvers.LinearProgramming
Solves integer and mixed-integer linear programs by branch and bound over linear relaxations.
For Beginners
Imagine choosing how many of each item to produce, where fractions are meaningless. The solver first ignores the whole-number rule and solves the easy version. If the answer happens to be whole numbers, it is done. If some quantity comes back as 3.4, it knows the true answer has that quantity at 3 or less, or at 4 or more — so it splits into those two worlds and explores each. The trick that makes this fast: the easy version’s answer is always at least as good as any whole-number answer beneath it, so if it is already worse than something found earlier, that entire world can be discarded unexamined.
How It Works
Implements branch and bound (Land and Doig, 1960) with best-bound node selection and branching on the most fractional variable. At each node the integrality requirement is dropped and the resulting linear program is solved:
- an infeasible relaxation means the node’s whole subtree is infeasible — prune;
- a relaxation bound no better than the best whole-number solution found so far means the
subtree cannot contain a better one — prune, because relaxing constraints can only improve the objective, so the relaxation is always at least as good as anything below it;
- an all-integral relaxation solution is a genuine candidate — record it;
- otherwise pick a variable sitting at a fractional value
vand split the node into
x ≤ ⌊v⌋ and x ≥ ⌈v⌉, which excludes the fractional point without excluding any
whole-number one.
Because relaxation bounds prune whole subtrees, the search usually visits a small fraction of the exponentially many possibilities — this bounding step is the entire reason branch and bound is practical.
Constructors
| Constructor | Summary |
|---|---|
BranchAndBoundSolver(BranchAndBoundSolverOptions options, ILinearProgramSolver<T> relaxationSolver) |
Creates a branch-and-bound solver. |
Methods
| Method | Summary |
|---|---|
LinearProgramSolution<T> Solve(IntegerProgram<T> program) |
Solves an integer or mixed-integer linear program. |