Publication Type

Working Paper

Version

publishedVersion

Publication Date

7-2015

Abstract

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.

Keywords

distribution approximation, persistency, Stein’s Identity, project management, fill rate, G/G/1 queue, transient solution

Discipline

Business

Research Areas

Finance

Download

Included in

Business Commons

Share

COinS