Confidence Sets for the Sample Average Approximation of Stochastic Discrete Optimization Problems

We propose a method to build confidence sets for the solutions of stochastic discrete optimization problems solved through the sample average approximation method. By combining the concept of Model Confidence Set (MCS) with shrinkage estimation of large covariance matrices, we accommodate sampling mechanisms that allow for arbitrary dependence across alternatives, even when the number of alternatives is larger than the sample size, and deliver confidence sets asymptotically containing the solution set with probability at least 1-α for predetermined α. We derive bounds for the error induced by replacing the true covariance matrix with an estimator and characterize the impact of this error on the asymptotic distribution of the MCS test statistics. We test the theoretical properties of our set estimator in finite samples through an extensive Monte Carlo experiment involving the computation of the covariance matrix using different shrinkage estimators. This research is the first to provide generally applicable measures of uncertainty in discrete optimization. Whenever a stochastic discrete optimization problem is solved using the sample average approximation method, the confidence set should be reported alongside the solution in order to provide a measure of uncertainty. The main contribution of the paper is to offer, for the first time, a method for computing confidence sets for the solutions of stochastic discrete optimization problems. We also derive a bound on the accuracy of the asymptotic distribution for a class of test statistics involving covariance matrices estimated with non-standard estimators.