Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-generatedPipeline-generated
How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

  • Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
  • AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
  • AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

A bounded mixed-integer gap certificate proves global epsilon-optimality

Statement

Suppose Bounded mixed-integer branch and bound with a finite enumeration fallback returns a feasible incumbent with verified upper bound U and a complete ledger of all nonempty terminal mixed nodes, each with lower bound ℓN valid on every feasible point in that node. Let L be the least ledger bound. If U−L≤ε, then the incumbent (x^,z^) satisfies f(x^,z^)−inf⁡(x,z)∈C∩(X×Z)f(x,z)≤ε. If every terminal node is certified empty, then the mixed feasible set is empty. The conclusion applies both to the branch tree and to the fallback only when every bounded integer assignment has a complete continuous ledger.

Facts & Assumptions

Given: Finite bounded integer box Z, continuous box X, the mixed-integer algorithm's branch/ledger invariants, valid node lower bounds, feasible incumbent, and tolerance ε>0.

[F1]

Integer branching at a median partitions its finite integer interval into disjoint children whose union is the parent; continuous midpoint children cover their parent. Bounded mixed-integer branch and bound with a finite enumeration fallback

[F2]

On a node whose real-hull feasible set is nonempty, a certified convex relaxation with verified coefficient/domain enclosures, a dual-feasible pair (λ,ν), and a verified real ℓ≤q(λ,ν) give a lower bound on every original feasible objective value. In particular the bound holds at every integer-feasible point of that node. No infimum is asserted for an empty feasible node. A verified dual certificate for a McCormick relaxation is a valid global lower bound

[F3]

In the enumeration fallback, each fixed integer assignment is passed to the continuous spatial algorithm, whose terminal boxes cover that assignment's continuous box, retaining certified-empty leaves with their proofs. Finite-budget certified spatial branch and bound

[F4]

Each continuous leaf lower bound is at most the objective at every feasible point of that leaf (vacuously when the leaf is empty), and each witness is feasible with objective at most its reported upper bound. Certified lower, upper, and emptiness bounds on a box

Proof

1.1givenF1F3induction

The root node contains every feasible pair in X×Z; the dummy-singleton representation, when used, is bijective and preserves objective and constraint values. Each integer branch preserves the union of the allowed integer values by [F1], and each continuous branch covers its parent box by [F1]. Removing a node only with an emptiness proof cannot remove a feasible pair. Induction on the finite number of expansions shows every feasible pair lies in a nonempty terminal node, or in one of the fixed-z continuous ledgers of the fallback.

2.1step 1.1F2F4algebra

For any feasible pair (x,z) choose its terminal node or fallback leaf as in step 1.1. For a main-tree node, the point (x,z) makes the real-hull feasible set nonempty, and the algorithm accepts a relaxation bound only with the certified relaxation, dual feasibility, and verified dual-value lower bound required by [F2]; hence its lower bound is at most f(x,z). For a fixed-z continuous leaf the same pointwise inequality follows from [F4]. Since L is the least bound over the complete global ledger, L≤f(x,z) for every feasible pair, hence L≤f∗.

3.1givenstep 2.1algebra∎

The feasible incumbent satisfies f(x^,z^)≤U. The certificate condition then gives f(x^,z^)≤U≤L+ε≤f∗+ε, proving the global gap claim. If every terminal node is certified empty, step 1.1 shows no feasible pair exists.

Depends on

Used by

Dependency tree · two levels

12 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources