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.

Finite-budget spatial branch and bound always returns a declared status

Statement

For every admissible finite oracle call and every positive integer budget $N$ , Finite-budget certified spatial branch and bound terminates after at most $N$ calls and returns exactly one of: a verified epsilon-global certificate, a certified infeasibility result, or an inconclusive budget/oracle status.

Facts & Assumptions

Given: The algorithm inputs and statuses in Finite-budget certified spatial branch and bound, with $N \in N$ , $N \geq 1$ , and an oracle that finishes each call in finite time or returns its explicit unavailable status.

[F1]

One oracle call is charged for each evaluated leaf; before any call, a counter already equal to $N$ makes the algorithm return the recorded ledger with status budget-exhausted. Finite-budget certified spatial branch and bound

[F2]

A box report with an unavailable required field makes no lower-bound or feasibility claim. Certified lower, upper, and emptiness bounds on a box

Proof

1.1givenF1algebra

At the start of a call, if the counter is $N$ the algorithm returns by [F1]. Otherwise it consumes exactly one unit for that call; every branch either schedules a finite two-child list or reaches a stated return condition.

2.1givenstep 1.1F2algebra∎

After at most $N$ evaluations, either a certificate, infeasibility result, or oracle status has already returned, or another call is required and the pre-call guard returns budget-exhausted. Each oracle call terminates by the Given condition, and each unavailable report has the explicit no-claim meaning in [F2], so the procedure terminates within at most $N$ calls.

Depends on

Used by

Finite-budget bounded mixed-integer branch and bound terminates Theorem

Dependency tree · two levels

4 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

Arnold Neumaier, Complete Search in Continuous Global Optimization and Constraint Satisfaction, §12 (standard reference, not scraped)