OPTFIN.ORGMultidisciplinary Research Laboratory for Operations Research and AI
Sign in

You are browsing anonymously. A verified sign-in is required before any personal or project data can appear.

IMPLEMENTED_LOCAL_TESTEDInteger optimization

ALGORITHM ARTICLE

Binary branch and bound

Problem. Exact optimization of a small binary linear program.

Core idea. LP relaxations bound subtrees; fractional variables split the search.

Procedure

  1. Solve the node relaxation.
  2. Prune infeasible or dominated nodes.
  3. Branch until the incumbent is certified.

Certificate. Feasible incumbent and exhausted/bounded tree.

Data structures and API

from optfin_orlab import BranchAndBound

solver = BranchAndBound()
result = solver.solve(...)

Complexity. Exponential in the worst case

Limits. The public solver targets small educational models.

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.
  • CorrectnessFeasible incumbent and exhausted/bounded tree.
  • ComplexityExponential in the worst case
  • Operational limitThe public solver targets small educational models.
  • ReproductionSource, executable test and evidence route remain linked.
View sourceOpen executable testReproduce evidence

LUNA ACADEMIC

Continue this algorithm in one research conversation.

Ask for the paper trail, executable test, source explanation, or a reproducibility plan for Binary branch and bound.

Open Luna for this algorithm

Back to the algorithm blog