← All setups

Bounded Mixed-Integer Linear Optimization

Descriptions may be stale. Consult the linked Lean sources.

Bounded Mixed-Integer Linear Optimization

We consider minimizing a linear objective f:Rp×Rq→R over integer variables in Zp and continuous variables in Rq, where p,q≥0 are integers. Feasibility is specified by finitely many linear inequalities and finite integer bounds on the integer variables. The continuous relaxation has an objective bounded below on its feasible set. For any queried integer box, the oracle returns an exact optimizer of the corresponding continuous relaxation or reports infeasibility. The goal is an exact mixed-integer optimizer, or a correct infeasibility report, for every realization of any randomness.

Write the objective and feasible set as f(z,y)=c⊤z+d⊤y,F={(z,y)∈Zp×Rq:Az+Gy≤b, ℓ≤z≤u}. The optimization problem is min(z,y)∈Ff(z,y). Here m≥0 is an integer, A∈Rm×p, G∈Rm×q, b∈Rm, c∈Rp, d∈Rq, and ℓ,u∈Zp. All vector inequalities are componentwise. The algorithm receives all of these dimensions, coefficients, and bounds.

For a queried box β=(a,h)∈Zp×Zp, define its relaxation feasible set by Rβ={(z,y)∈Rp×Rq:Az+Gy≤b, ℓ≤z≤u, a≤z≤h}. Thus each query imposes its bounds in addition to the original bounds.

Our assumptions:

Assumption 1 (Lower bounded relaxation). There exists L∈R such that f(z,y)≥Lfor every (z,y)∈R(ℓ,u).

Assumption 2 (Exact relaxation oracle). Queries may be any pair β∈Zp×Zp. The oracle reports infeasibility exactly when Rβ is empty. 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 reply, including every choice among multiple optimizers.

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

Results

Minimize c⊤z+d⊤y subject to Az+Gy≤b, z∈Zp, y∈Rq, and ℓ≤z≤u, with real data and integer bounds. The root LP relaxation has objective bounded below. Each exact oracle call solves the relaxation with an additional integer box, returning any optimum or reporting infeasibility. The target is an exact global optimum or a correct infeasibility report for every seed and admissible oracle.

Exact bounded mixed-integer linear optimization: BoundedMixedIntegerLinear.
Result Oracle complexity Novelty Limitations
(1) LpBranchAndBoundMilp (Ours) (review) O(N) exact LP calls
(2) Branch-and-bound (Conforti et al. 2014) Exact node-LP oracle (1): Formalizes the classical finite-termination guarantee; no established complexity, scope, or output improvement.
(3) Exhaustive enumeration (derived bound) (Conforti et al. 2014) O(N) exact LP calls; one fixed-integer LP per box point (1): Matches known rate on the same setup and oracle. (1): Worst-case budget approaches twice the enumeration cost as N→∞; no quantified pruning gain.

Abbr: N=∏j=1p(uj−ℓj+1)+ is the number of integer box points; (t)+=max{t,0}. LP: linear program. Costs count complete exact LP solves, not arithmetic or bit operations.

Conforti, Michele, Gérard Cornuéjols, and Giacomo Zambelli. 2014. Integer Programming. Vol. 271. Graduate Texts in Mathematics. Springer. https://doi.org/10.1007/978-3-319-11008-0.

Lean setup