Business Commons^™

Mixed 0-1 Linear Programs Under Objective Uncertainty: A Completely Positive Representation, Karthik Natarajan, Chung-Piaw Teo, Zhichao Zheng

Research Collection Lee Kong Chian School Of Business

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 is 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 …