Descriptions may be stale. Consult the linked Lean sources.
Bounded Mixed-Integer
Linear Optimization
We consider minimizing a linear objective
over integer variables in and continuous variables in
, where 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 The optimization problem is Here
is an integer, , , , , , and . All vector
inequalities are componentwise. The algorithm receives all of these
dimensions, coefficients, and bounds.
For a queried box ,
define its relaxation feasible set by Thus each
query imposes its bounds in addition to the original bounds.
Our assumptions:
Assumption 1 (Lower bounded relaxation). There
exists such that
Assumption 2 (Exact relaxation oracle). Queries may
be any pair .
The oracle reports infeasibility exactly when is empty. Otherwise
it returns a point satisfying 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 .
An infeasibility report must certify ; a returned pair
must satisfy This exact success requirement holds for every
realization of the algorithm’s and oracle’s randomness.