Abstract
This paper studies the expected optimal value of a mixed 0-1 programming problem with uncertain objective coefficients following a joint distribution. We assume that the true distribution is not known exactly, but a set of independent samples can be observed. Using the Wasserstein metric, we construct an ambiguity set centered at the empirical distribution from the observed samples and containing the true distribution with a high statistical guarantee. The problem of interest is to investigate the bound on the expected optimal value over the Wasserstein ambiguity set. Under standard assumptions, we reformulate the problem into a copositive program, which naturally leads to a tractable semidefinite-based approximation. We compare our approach with a moment-based approach from the literature on three applications. Numerical results illustrate the effectiveness of our approach.
| Language | English (US) |
|---|---|
| Pages | 111-134 |
| Number of pages | 24 |
| Journal | Computational Management Science |
| Volume | 15 |
| Issue number | 1 |
| DOIs | |
| State | Published - Jan 1 2018 |
Fingerprint
Keywords
- Copositive programming
- Distributionally robust optimization
- Semidefinite programming
- Wasserstein metric
Cite this
A data-driven distributionally robust bound on the expected optimal value of uncertain mixed 0-1 linear programming. / Xu, Guanglin; Burer, Samuel.
In: Computational Management Science, Vol. 15, No. 1, 01.01.2018, p. 111-134.Research output: Contribution to journal › Article
}
TY - JOUR
T1 - A data-driven distributionally robust bound on the expected optimal value of uncertain mixed 0-1 linear programming
AU - Xu,Guanglin
AU - Burer,Samuel
PY - 2018/1/1
Y1 - 2018/1/1
N2 - This paper studies the expected optimal value of a mixed 0-1 programming problem with uncertain objective coefficients following a joint distribution. We assume that the true distribution is not known exactly, but a set of independent samples can be observed. Using the Wasserstein metric, we construct an ambiguity set centered at the empirical distribution from the observed samples and containing the true distribution with a high statistical guarantee. The problem of interest is to investigate the bound on the expected optimal value over the Wasserstein ambiguity set. Under standard assumptions, we reformulate the problem into a copositive program, which naturally leads to a tractable semidefinite-based approximation. We compare our approach with a moment-based approach from the literature on three applications. Numerical results illustrate the effectiveness of our approach.
AB - This paper studies the expected optimal value of a mixed 0-1 programming problem with uncertain objective coefficients following a joint distribution. We assume that the true distribution is not known exactly, but a set of independent samples can be observed. Using the Wasserstein metric, we construct an ambiguity set centered at the empirical distribution from the observed samples and containing the true distribution with a high statistical guarantee. The problem of interest is to investigate the bound on the expected optimal value over the Wasserstein ambiguity set. Under standard assumptions, we reformulate the problem into a copositive program, which naturally leads to a tractable semidefinite-based approximation. We compare our approach with a moment-based approach from the literature on three applications. Numerical results illustrate the effectiveness of our approach.
KW - Copositive programming
KW - Distributionally robust optimization
KW - Semidefinite programming
KW - Wasserstein metric
UR - http://www.scopus.com/inward/record.url?scp=85040698959&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85040698959&partnerID=8YFLogxK
U2 - 10.1007/s10287-018-0298-9
DO - 10.1007/s10287-018-0298-9
M3 - Article
VL - 15
SP - 111
EP - 134
JO - Computational Management Science
T2 - Computational Management Science
JF - Computational Management Science
SN - 1619-697X
IS - 1
ER -