This paper is motivated by the following question: How to construct good approximation for the distribution of the solution value to linear optimization problem when the objective function is random? More generally, we consider any mixed zero-one linear optimization problem, and develop an approach to approximate the distribution of its optimal value when the random objective coefficients follow a multivariate normal distribution. Linking our model to the classical Stein’s Identity, we show that the least squares normal approximation of the random optimal value can be computed by solving the persistency problem, first introduced by Bertsimas et al. (2006). We further extend our method to construct a least squares quadratic estimator to improve the accuracy of the approximation, in particular, to capture the skewness of the objective. We use this approach to construct good estimators for (a) the fill rate of an inventory system in a finite horizon; (b) the waiting time distribution of the nth customer in a G/G/1 system when the arrival rate equals the service rate; and (c) the project completion time distribution.
distribution approximation, persistency, Stein’s Identity, project management, fill rate, G/G/1 queue, transient solution
ZHENG, Zhichao; NATARAJAN, Karthik; and TEO, Chung-Piaw.
Least squares approximation to stochastic optimization problems. (2015). Research Collection Lee Kong Chian School Of Business.
Available at: http://ink.library.smu.edu.sg/lkcsb_research/4524