Please use this identifier to cite or link to this item: https://doi.org/10.1287/opre.1110.0918
Title: Mixed 0-1 linear programs under objective uncertainty: A completely positive representation
Authors: Natarajan, K.
Teo, C.P. 
Zheng, Z.
Keywords: Completely positive program
Mixed 0-1 linear program
Moments
Issue Date: 2011
Source: Natarajan, K., Teo, C.P., Zheng, Z. (2011). Mixed 0-1 linear programs under objective uncertainty: A completely positive representation. Operations Research 59 (3) : 713-728. ScholarBank@NUS Repository. https://doi.org/10.1287/opre.1110.0918
Abstract: In this paper, we analyze mixed 0-1 linear programs under objective uncertainty. The mean vector and the second-moment matrix of the nonnegative objective coefficients are assumed to be known, but the exact form of the distribution is unknown. Our main result shows that computing a tight upper bound on the expected 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 can be extended to deal with uncertainty in the moments and more complicated objective functions. Examples from order statistics and project networks highlight the applications of the model. Our belief is that the model will open an interesting direction for future research in discrete and linear optimization under uncertainty. © 2011 INFORMS.
Source Title: Operations Research
URI: http://scholarbank.nus.edu.sg/handle/10635/44016
ISSN: 0030364X
DOI: 10.1287/opre.1110.0918
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

17
checked on Dec 13, 2017

WEB OF SCIENCETM
Citations

11
checked on Nov 16, 2017

Page view(s)

42
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.