Title: Beyond Worst-case: A Probabilistic Analysis of Affine Policies in Dynamic Optimization,
Abstract: Affine policies (or control) are widely used as a solution approach in
dynamic optimization where computing an optimal adjustable solution is usually
intractable. While the worst case performance of affine policies can be
significantly bad, the empirical performance is observed to be near-optimal for
a large class of problem instances. For instance, in the two-stage dynamic
robust optimization problem with linear covering constraints and uncertain
right hand side, the worst-case approximation bound for affine policies is
$O(\sqrt m)$ that is also tight (see Bertsimas and Goyal (2012)), whereas
observed empirical performance is near-optimal. In this paper, we aim to
address this stark-contrast between the worst-case and the empirical
performance of affine policies. In particular, we show that affine policies
give a good approximation for the two-stage adjustable robust optimization
problem with high probability on random instances where the constraint
coefficients are generated i.i.d. from a large class of distributions; thereby,
providing a theoretical justification of the observed empirical performance. On
the other hand, we also present a distribution such that the performance bound
for affine policies on instances generated according to that distribution is
$\Omega(\sqrt m)$ with high probability; however, the constraint coefficients
are not i.i.d.. This demonstrates that the empirical performance of affine
policies can depend on the generative model for instances.