Mixed 0-1 Linear Programs Under Objective Uncertainty: A Completely Positive Representation

Karthik Natarajan (), Chung Piaw Teo () and Zhichao Zheng ()
Additional contact information
Karthik Natarajan: Department of Management Sciences, City University of Hong Kong, Hong Kong
Chung Piaw Teo: Department of Decision Sciences, NUS Business School, National University of Singapore, Singapore 117591
Zhichao Zheng: Department of Decision Sciences, NUS Business School, National University of Singapore, Singapore 117591

Operations Research, 2011, vol. 59, issue 3, 713-728

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.

Keywords: mixed 0-1 linear program; moments; completely positive program (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (21)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1110.0918 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:59:y:2011:i:3:p:713-728

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().