Optimization Online


Semidefinite Programming Reformulation of Completely Positive Programs: Range Estimation and Best-Worst Choice Modeling

Karthik Natarajan(natarajan_karthik***at***sutd.edu.sg)
Chung-Piaw Teo(bizteocp***at***nus.edu.sg)

Abstract: We show that the worst case moment bound on the expected optimal value of a mixed integer linear program with a random objective c is closely related to the complexity of characterizing the convex hull of the points CH{(1 x) (1 x)': x \in X} where X is the feasible region. In fact, we can replace the completely positive programming characterization of the moment bound on X, with an associated semide finite program, provided we have a compact reformulation of this convex hull. We illustrate the usefulness of the semidefi nite programming bounds in estimating the expected range of random variables with two applications arising in random walks and best-worst choice models.

Keywords: Semidefinite program; Completely positive program; Moment bounds

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

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


Download: [PDF]

Entry Submitted: 03/07/2014
Entry Accepted: 03/08/2014
Entry Last Modified: 03/07/2014

Modify/Update this entry

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


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