When Is Two-Stage Sample Robust Optimization Asymptotically Optimal? A Simple Perspective

Abstract

Two-stage sample robust optimization with linear decision rules is a standard data-driven approach to two-stage stochastic linear programs with unknown distributions. \cite{bertsimas2022two} established that this approach is asymptotically optimal under several conditions. Most conditions are mild, but one imposes a technical requirement on the recourse system. Whether this condition is implied by the others was left as an open question. We resolve this open question through a geometric feature of the support set: simpleness, the property that every vertex is incident to exactly as many edges as the dimension of the support. For simple support sets, the technical condition is automatic, and asymptotic optimality holds under the remaining standard assumptions. For every non-simple support, we construct a recourse system that is feasible everywhere in the support but violates the technical condition, and this construction resolves the open question. We further characterize the simpleness of one-sided and two-sided budgeted uncertainty sets and identify when budget perturbations can restore simpleness. We also develop a polynomial-time algorithm that certifies the technical condition at a given vertex using its incident edge directions. Numerical experiments on newsvendor and network lot-sizing problems illustrate the characterization and the effectiveness of the verification algorithm.

arXiv comment63 pages, 6 figures