On the power and limitations of affine policies in two-stage adaptive optimization

摘要

We consider a two-stage adaptive linear optimization problem under right hand side uncertainty with a min–max objective and give a sharp characterization of the power and limitations of affine policies (where the second stage solution is an affine function of the right hand side uncertainty). In particular, we show that the worst-case cost of an optimal affine policy can be ${Omega(m^{1/2-delta})}$ times the worst-case cost of an optimal fully-adaptable solution for any δ 0, where m is the number of linear constraints. We also show that the worst-case cost of the best affine policy is ${O(sqrt m)}$ times the optimal cost when the first-stage constraint matrix has non-negative coefficients. Moreover, if there are only k ≤ m uncertain parameters, we generalize the performance bound for affine policies to ${O(sqrt k)}$ , which is particularly useful if only a few parameters are uncertain. We also provide an ${O(sqrt k)}$ -approximation algorithm for the general case without any restriction on the constraint matrix but the solution is not an affine function of the uncertain parameters. We also give a tight characterization of the conditions under which an affine policy is optimal for the above model. In particular, we show that if the uncertainty set, ${{mathcal U} subseteq {mathbb R}^m_+}$ is a simplex, then an affine policy is optimal. However, an affine policy is suboptimal even if ${{mathcal U}}$ is a convex combination of only (m + 3) extreme points (only two more extreme points than a simplex) and the worst-case cost of an optimal affine policy can be a factor (2 − δ) worse than the worst-case cost of an optimal fully-adaptable solution for any δ 0.