Limit Laws for Empirical Optimal Solutions in Stochastic Linear Programs

Understand

We consider a general linear program in standard form whose right-hand side constraint vector is subject to random perturbations.

• This defines a stochastic linear program for which, under general conditions, we characterize the fluctuations of the corresponding empirical optimal solution by a central limit-type theorem.
• Our approach relies on the combinatorial nature and the concept of degeneracy inherent in linear programming, in strong contrast to well-known results for smooth stochastic optimization programs.
• In particular, if the corresponding dual linear program is degenerate the asymptotic limit law might not be unique and is determined from the way the empirical optimal solution is chosen.