Theorem 5 — the ε-approximation (6_ε) is equivalent to the mixed-integer bilinear program (7)

Consider the two-stage robust binary program with uncertain constraints: data $C,Q,T,W,H$, an uncertainty set $\Xi=\{\xi\in\mathbb R^Q:A\xi\le b\}$ that is nonempty and bounded, $\mathcal X\subseteq\{0,1\}^N$, $\mathcal Y\subseteq\{0,1\}^M$, and $K$ second-stage policies. Fix $\epsilon>0$, and let $\varphi_\epsilon$ be the objective of the approximate problem

Theorem 5 states that $(6_\epsilon)$ is equivalent to the mixed-integer bilinear program (7), which minimizes $\tau$ subject to $x\in\mathcal X$, $y^k\in\mathcal Y$, $\tau\in\mathbb R$, and for each $\ell\in\partial\mathcal L$ (resp. $\ell\in\mathcal L_+$) the dual constraints on $\lambda(\ell)\in\Delta_K(\ell)$, $\alpha(\ell)$, $\beta^k(\ell)$, $\gamma(\ell)$ (resp. $\alpha(\ell)$, $\gamma(\ell)$) described in the definition of program (7).

Precisely:

1. for every decision $(x,\{y^k\})\in\mathcal X\times\mathcal Y^K$, a real $\tau$ is feasible in (7) together with this decision if and only if $\tau\ge\varphi_\epsilon(x,\{y^k\})$; consequently

and the infimum is attained whenever it is finite; 2. the optimal values of $(6_\epsilon)$ and (7) coincide.

The theorem converts the approximate K-adaptability problem, whose objective involves suprema over finitely many polyhedral sets, into a single finite program whose only nonlinearities are products of a binary variable with a continuous one, so that it can be linearized into a mixed-integer linear program.

Formalization Note All values are in the extended reals: the infimum of an empty set of $\tau$ is $+\infty$ (a decision for which some $\Xi_\epsilon(\ell)$, $\ell\in\mathcal L_+$, is nonempty), and it is $-\infty$ when every real $\tau$ is feasible (every $\Xi_\epsilon(\ell)$ is empty). "Equivalent" is pinned down as the per-decision identity above together with equality of optimal values.