← All setups

Lp Branch And Bound Milp — Bounded Mixed-Integer Linear Optimization

Descriptions may be stale. Consult the linked Lean sources.

Bounded Mixed-Integer Linear Optimization · Lean proof

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.

Proved result

2⋅(∏j=0p−1max{hi(j)−lo(j)+1,0})−1

OracleTemplate.Convergence LongTails.Setups.BoundedMixedIntegerLinear.spec
  OracleTemplate.BoundedMixedIntegerLinear.budget

Relevant previous results

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