On the performance of affine policies for two-stage adaptive optimization: a geometric perspective (Q747776)

The two-stage adaptive robust linear optimization problem \(\Pi_{\mathrm{Adopt}}(U)\), given by \(z_{\mathrm{Adopt}}(U)=\min c^Tx + \max_{b\in U}\min_{y(b)} d^Ty(b)\), subject to \(Ax+By(b) \geq b\) for all \(b\in U\) and \(x,y(b)\geq 0\) is considered, where \(A,B\) are matrices, \(c,d\) are vectors and \(U\subset \mathbb R^m_+\) is a convex, compact uncertainty set of possible values \(b\). Using affine policies \(y(b)=Pb+q\), the authors get a tractable problem with objective \(z_{\mathrm{Aff}}(U)\) and construct for the intractable problem \(\Pi_{\mathrm{Adopt}}(U)\) a priory bounds according to \(z_{\mathrm{Adopt}}(U)\leq z_{\mathrm{Aff}}(U)\leq (\lambda(1+\rho/s)/(\lambda+\rho/s)z_{\mathrm{Adopt}}(U)\). Here \(s={\mathrm{sym}}(U)\in [1/m,1]\) is an improved measure of symmetry taking into account the geometric structure of \(U\), \(\rho\) is a translation factor of \(U\) towards the origin inside of \(\mathbb R^m_+\) and \(\lambda\geq 1\) is the simplex dilation factor with respect to an inscribed and circumscribed simplex of \(U\). The parameters \(s,\rho,\lambda\) are determined for a couple of important examples of \(U\) showing the significant improvement of the new a priori bound in contrast to the robust bound in [\textit{D. Bertsimas} et al., Math. Oper. Res. 36, No. 1, 24--54 (2011; Zbl 1218.90142)]. In case of an inventory problem, the authors demonstrate that their new a priory bound is competitive to known a posteriori bounds. The main results are shown in detail.