A data-driven distributionally robust bound on the expected optimal value of uncertain mixed 0-1 linear programming

Guanglin Xu, Samuel Burer

Research output: Contribution to journalArticle

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.

LanguageEnglish (US)
Pages111-134
Number of pages24
JournalComputational Management Science
Volume15
Issue number1
DOIs
StatePublished - Jan 1 2018

Fingerprint

Linear programming
Semidefinite programming
Guarantee
Nature
Joint distribution
Approximation
Empirical distribution
Coefficients
Germany
Programming

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 journalArticle

@article{26107325cceb48b2b969c5e922691c69,
title = "A data-driven distributionally robust bound on the expected optimal value of uncertain mixed 0-1 linear programming",
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.",
keywords = "Copositive programming, Distributionally robust optimization, Semidefinite programming, Wasserstein metric",
author = "Guanglin Xu and Samuel Burer",
year = "2018",
month = "1",
day = "1",
doi = "10.1007/s10287-018-0298-9",
language = "English (US)",
volume = "15",
pages = "111--134",
journal = "Computational Management Science",
issn = "1619-697X",
publisher = "Springer Verlag",
number = "1",

}

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 -