← All setups

Best Bound Hidden Milp — Hidden Mixed-Integer Linear Optimization

Descriptions may be stale. Consult the linked Lean sources.

Hidden Mixed-Integer Linear Optimization · Lean proof

Hidden Mixed-Integer Linear Optimization

We consider linear optimization over Zp×Rq, where p,q are nonnegative integers, with known objective coefficients and finite integer bounds but hidden linear inequality constraints. Either the continuous relaxation is infeasible, or hidden nonnegative constraint multipliers cancel the continuous-variable coefficients in the Lagrangian. Given an integer box, the oracle returns an exact optimizer of the continuous relaxation restricted to that box and the original bounds, or reports infeasibility. The goal is to return an exact mixed-integer global optimizer, or correctly report infeasibility, for every realization of any algorithm and oracle randomness.

Write the objective as f(z,y)=c⊤z+d⊤y, where c∈Rp and d∈Rq. The problem is min(z,y)∈Ff(z,y),F={(z,y)∈Zp×Rq:Az+Gy≤b, ℓ≤z≤u}. Here m≥0 is an integer, A∈Rm×p, G∈Rm×q, b∈Rm, and ℓ,u∈Zp. All vector inequalities are componentwise. The algorithm receives only p,q,c,d,ℓ,u; the hidden data m,A,G,b and multiplier vector λ∈Rm may enter the oracle-call budget but are not algorithm inputs.

For any query box β=(a,h)∈Zp×Zp, define Rβ={(z,y)∈Rp×Rq:Az+Gy≤b, ℓ≤z≤u, a≤z≤h}. In particular, R(ℓ,u) is the full continuous relaxation. Query endpoints need not lie within the original bounds or be ordered; the intersection above determines feasibility.

Our assumptions:

Assumption 1 (Hidden multiplier certificate). The hidden parameters satisfy the disjunction (λ≥0  and  d+G⊤λ=0)orR(ℓ,u)=∅.

Assumption 2 (Exact relaxation oracle). For every query box β, the oracle reports infeasibility exactly when Rβ=∅. Otherwise it returns a point (zβ,yβ) satisfying (zβ,yβ)∈Rβ,f(zβ,yβ)≤f(z,y)for every (z,y)∈Rβ. These requirements hold for every query history and every realization of oracle randomness; the choice among optimizers may depend on both. Algorithm randomness is independent of oracle randomness.

After the allotted oracle calls, the output is either an infeasibility report or a pair (z¯,y¯)∈Zp×Rq. An infeasibility report must satisfy F=∅; a returned pair must satisfy (z¯,y¯)∈F,f(z¯,y¯)≤f(z,y)for every (z,y)∈F. The corresponding requirement must hold for every realization of algorithm and oracle randomness.

Proved result

min{2⋅(∏j=0p−1max{hi(j)−lo(j)+1,0})−1,1+4⋅p⋅|goodPoints(P)|}

OracleTemplate.Convergence LongTails.Setups.HiddenMixedIntegerLinear.spec OracleTemplate.HiddenMixedIntegerLinear.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.