-

 

 

 




Optimization Online





 

MIXED ZERO-ONE LINEAR PROGRAMS UNDER OBJECTIVE UNCERTAINTY: A COMPLETELY POSITIVE REPRESENTATION

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

Abstract: In this paper, we analyze mixed 0-1 linear programs under objective uncertainty using a moments based approach. Suppose the first moment vector and the second moment matrix of the nonnegative objective coefficients are known, but the exact form of the distribution is unknown. Our main result shows that computing the supremum of the expected optimal objective value of a mixed 0-1 linear program in maximization form with random objective is a completely positive program. This naturally leads to semidefinite programming relaxations that are solvable in polynomial time but provide weaker bounds. The result is extended to objective coefficients over Euclidean space, uncertain moments and more complicated objective functions. Examples from order statistics and project management highlight the applications of the model. Our belief is that this model will open an interesting dimension for further research in stochastic discrete and linear optimization.

Keywords: Mixed 0-1 linear program; Moments; Completely positive program

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

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Stochastic Programming

Citation:

Download: [PDF]

Entry Submitted: 08/06/2009
Entry Accepted: 08/07/2009
Entry Last Modified: 06/22/2011

Modify/Update this entry


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

 

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