ExampleConstruction: AI-generatedVerification: 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 engineering design has an exact mixed-integer gap certificate

Example

A manufacturer chooses a module count $z \in {0, 1, 2}$ and a normalized continuous setting $x \in [0, 1]$ . Set the tolerance to $ε = 1 / 10$ and the total node budget to $N = 4$ . The mixed relaxation oracle reports bound-unavailable on the root evaluation, which uses one call and triggers the enumeration fallback. The exact cost is $F (z, x) = (x - z / 2)^{2} + (z - 2)^{2} / 10.$ Encode the same feasible set in constrained mode with the redundant inequalities $- x \leq 0$ and $x - 1 \leq 0$ . The continuous box oracle may therefore return the feasible witness $x = z / 2$ rather than the unconstrained midpoint. Finite enumeration is the fallback for the mixed-integer relaxation oracle.

Facts & Assumptions

Given: The finite design set ${0, 1, 2} \times [0, 1]$ , the cost $F$ , $ε = 1 / 10$ , node budget $N = 4$ , a root mixed-relaxation result bound-unavailable, and Bounded mixed-integer branch and bound with a finite enumeration fallback. The constraint DAGs are $- x$ and $x - 1$ . Each fallback assignment receives one remaining call in constrained mode; its exact continuous root report returns the square-completion lower bound and an attaining feasible point.

[F1]

A complete mixed-integer ledger with feasible upper bound $U$ and valid lower bound $L$ is a global epsilon certificate when $U - L \leq ε$ . A bounded mixed-integer gap certificate proves global epsilon-optimality

Verification

1.1givenalgebra

For each fixed $z \in {0, 1, 2}$ , the square $(x - z / 2)^{2}$ is nonnegative, so $F (z, x) \geq (z - 2)^{2} / 10$ . The point $x = z / 2$ belongs to $[0, 1]$ and attains equality. Thus the exact fixed-integer minima are $2 / 5$ , $1 / 10$ , and $0$ , respectively.

2.1givenstep 1.1algebra

After the root mixed-relaxation call, the three remaining calls are allocated one to each assignment in lexicographic order. For $z = 0, 1, 2$ , the exact continuous root report gives the lower bound $2 / 5, 1 / 10, 0$ , respectively, and the feasible point $x = z / 2$ attains it. Thus the complete fallback ledger has $L = 0$ , and $(z, x) = (2, 1)$ gives $U = 0$ . The total gap is exactly zero, which is at most $ε$ .

3.1F1step 2.1algebra∎

Therefore $(2, 1)$ is globally optimal and is a zero-gap mixed-integer certificate. The proof uses finite enumeration and exact values; it makes no complexity claim for larger integer ranges.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

7 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 and 17 (standard reference, not scraped)