ALGORITHM ARTICLE
Branch and cut
Problem. Strengthen a binary branch-and-bound relaxation with valid inequalities.
Core idea. Remove fractional LP points without removing integer-feasible solutions.
Procedure
- Solve the LP relaxation.
- Separate zero-half, MIR and lifted-cover cuts.
- Add effective cuts before branching.
Certificate. Incumbent, cut ledger and bounded search tree.
Data structures and API
from optfin_orlab import BranchAndBound
solver = BranchAndBound()
result = solver.solve(..., use_cuts=True)Complexity. Problem-dependent; exponential worst case
Limits. Cuts do not guarantee a small tree.
OPTFIN AUDIT CHECKS
What has to reconcile before this method is trusted.
- DefinitionProblem, objective, inputs and output are explicit.
- Data structureThe public API and canonical source path are identified.
- CorrectnessIncumbent, cut ledger and bounded search tree.
- ComplexityProblem-dependent; exponential worst case
- Operational limitCuts do not guarantee a small tree.
- ReproductionSource, executable test and evidence route remain linked.
LUNA ACADEMIC
Continue this algorithm in one research conversation.
Ask for the paper trail, executable test, source explanation, or a reproducibility plan for Branch and cut.
Open Luna for this algorithm