Stochastic Programming and Approximation

Stochastic programming facilitates decision making under uncertainty. Unfortunately, it is usually impractical to find an optimal solution to a stochastic program. Confidence intervals on the optimal value, or optimal gap of a candidate solution, can be obtained using Monte Carlo approximations. However, the standard point estimate of the optimal value, or optimality gap, contains bias due to the nature of the sampling-based approximation. We provide a method to reduce this bias, and hence provide a better, i.e., tighter, confidence interval on the optimal value or a candidate solution's optimality gap. Our method requires less restrictive assumptions on the structure of the bias than previously-available estimators, and we establish desirable statistical properties of our estimators. Our estimators adapt to problem-specific properties, and we provide a family of estimators, which allows flexibility in choosing the level of aggressiveness for bias reduction. We compare our estimators with known techniques on test problems from the literature.