Optimization Online


Distribution of the Optimal Value of a Stochastic Mixed Zero-One Linear Optimization Problem under Objective Uncertainty

Karthik Natarajan (knataraj***at***cityu.edu.hk )
Chung-Piaw Teo (bizteocp***at***nus.edu.sg)
Zhichao Zheng (zhichao***at***nus.edu.sg)

Abstract: This paper is motivated by the question to approximate the distribution of the completion time of a project network with random activity durations. In general, we consider the mixed zero-one linear optimization problem under objective uncertainty, 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 best normal approximation of the random optimal value, under the L^2-norm, can be computed by solving the persistency problem, first introduced by Bertsimas et al. (2006). We further extend our method to the minimum quadratic regret problem, and show that for any general mixed zero-one linear optimization problem, the minimum quadratic regret solution can be computed by solving a related persistency problem. Extensive computational studies are presented to demonstrate the advantages of the new method.

Keywords: stochastic mixed zero-one linear optimization; persistency; distribution approximation; regret; completely positive programming; project management; portfolio selection

Category 1: Stochastic Programming

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Applications -- OR and Management Sciences



Entry Submitted: 06/20/2011
Entry Accepted: 06/20/2011
Entry Last Modified: 08/01/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society