Mixed 0-1 linear programs under objective uncertainty : A completely positive representation

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

34 Scopus Citations
View graph of relations

Author(s)

  • Karthik Natarajan
  • Chung Piaw Teo
  • Zhichao Zheng

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)713-728
Journal / PublicationOperations Research
Volume59
Issue number3
Publication statusPublished - May 2011

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.

Research Area(s)

  • Completely positive program, Mixed 0-1 linear program, Moments

Citation Format(s)

Mixed 0-1 linear programs under objective uncertainty : A completely positive representation. / Natarajan, Karthik; Teo, Chung Piaw; Zheng, Zhichao.

In: Operations Research, Vol. 59, No. 3, 05.2011, p. 713-728.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review