- Semidefinite Programming Reformulation of Completely Positive Programs: Range Estimation and Best-Worst Choice Modeling Karthik Natarajan(natarajan_karthiksutd.edu.sg) Chung-Piaw Teo(bizteocpnus.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 ) Citation: Download: [PDF]Entry Submitted: 03/07/2014Entry Accepted: 03/08/2014Entry Last Modified: 03/07/2014Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.