Descriptions may be stale. Consult the linked Lean sources.
Hidden Mixed-Integer
Linear Optimization
We consider linear optimization over , where
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 , where and . The problem is Here is an integer, , , , and . All vector
inequalities are componentwise. The algorithm receives only ; the hidden data and multiplier vector may enter the
oracle-call budget but are not algorithm inputs.
For any query box ,
define In
particular,
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
Assumption 2 (Exact relaxation oracle). For every
query box , the oracle reports
infeasibility exactly when .
Otherwise it returns a point satisfying 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 . An infeasibility report
must satisfy ; a returned pair
must satisfy The corresponding requirement must hold for every
realization of algorithm and oracle randomness.