← All setups

Hidden Mixed-Integer Linear Optimization

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

Minimize c⊤z+d⊤y subject to Az+Gy≤b, ℓ≤z≤u, z∈Zp, y∈Rq, with real data and integer bounds. Only p,q,c,d,ℓ,u are public. Either the root LP is infeasible or a hidden λ≥0 satisfies d+G⊤λ=0. Each box-LP call returns an exact optimizer or reports infeasibility, with arbitrary optimal-solution choices. The target is an exact mixed-integer optimum or a correct infeasibility report for every execution.

Exact hidden mixed-integer linear optimization: HiddenMixedIntegerLinear.
Result Oracle complexity Novelty Limitations
(1) BestBoundHiddenMilp (Ours) (⋆⋆) (review) O(min{N,1+p|Gλ|}) box-LP calls
(2) Best-bound B&B (Dey et al. 2021, Theorem 3) O(1+p|Gλ∗|) LP calls. Special case: pure binary IP, q=0, [ℓ,u]=[0,1]p; optimal root dual λ∗. (1): Scope extends to bounded integers and continuous variables, with range-free factor p and any feasible λ. Matches the binary rate at λ=λ∗. (1): Good-point term has twice the leading constant on the binary overlap.
(3) Classical finite-tree bound (LongTails, n.d.) O(N) box-LP calls (full setup; bounded-below root LP). (1): Gap-dependent saving when p|Gλ|=o(N); retains the finite-tree cap. Hidden constraints suffice.
(4) Enumeration, derived bound (LongTails, n.d.) O(N) box-LP calls, one degenerate box per integer point (full setup). (1): Fewer calls if 1+4p|Gλ|<N. Binary example: |Gλ|≤p3 gives O(p4) versus O(2p); at p=60, about 5⋅107 versus 260. (1): Up to twice the call bound when |Gλ|≈N.

Abbr: LP: linear program; IP: integer program; B&B: branch-and-bound. N=∏j=1pmax{uj−ℓj+1,0}; OPT is the mixed-integer optimal value, with OPT=+∞ for infeasibility; Gλ={z∈Zp∩[ℓ,u]:(c+A⊤λ)⊤z−λ⊤b≤OPT}. λ∗ denotes an optimal root-LP dual multiplier. Costs count LP solves, not arithmetic operations.

Dey, Santanu S., Yatharth Dubey, and Marco Molinaro. 2021. Branch-and-Bound Solves Random Binary IPs in Polytime. https://doi.org/10.48550/arXiv.2007.15192.
LongTails: LpBranchAndBoundMilp. n.d. Repository convergence theorem and oracle budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/LpBranchAndBoundMilp.lean.

Lean setup