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 … Read more

Mixed Zero-one Linear Programs Under Objective Uncertainty: A Completely Positive Representation

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 … Read more

Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion

In this paper, we propose a semidefinite optimization (SDP) based model for the class of minimax two-stage stochastic linear optimization problems with risk aversion. The distribution of the second-stage random variables is assumed to be chosen from a set of multivariate distributions with known mean and second moment matrix. For the minimax stochastic problem with … Read more

A Persistency Model and Its Applications in Choice Modeling

Given a discrete optimization problem $Z(\mb{\tilde{c}})=\max\{\mb{\tilde{c}}’\mb{x}:\mb{x}\in \mathcal{X}\}$, with objective coefficients $\mb{\tilde{c}}$ chosen randomly from a distribution ${\mathcal{\theta}}$, we would like to evaluate the expected value $E_\theta(Z(\mb{\tilde{c}}))$ and the probability $P_{\mathcal{\theta}}(x^*_i(\mb{\tilde{c}})=k)$ where $x^*(\mb{\tilde{c}})$ is an optimal solution to $Z(\mb{\tilde{c}})$. We call this the persistency problem for a discrete optimization problem under uncertain objective, and $P_{\mathcal{\theta}}(x^*_i(\mb{\tilde{c}})=k)$, the … Read more

From CVaR to Uncertainty Set: Implications in Joint Chance Constrained Optimization

In this paper we review the different tractable approximations of individual chance constraint problems using robust optimization on a varieties of uncertainty set, and show their interesting connections with bounds on the condition-value-at-risk CVaR measure popularized by Rockafellar and Uryasev. We also propose a new formulation for approximating joint chance constrained problems that improves upon … Read more