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

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.

Article

Download

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