DISTRIBUTIONALLY ROBUST TWO-STAGE STOCHASTIC PROGRAMMING

Daniel Duque; Sanjay Mehrotra; DAVID P. MORTON

doi:10.1137/20M1370227

DISTRIBUTIONALLY ROBUST TWO-STAGE STOCHASTIC PROGRAMMING

Daniel Duque, Sanjay Mehrotra, DAVID P. MORTON

Industrial Engineering and Management Sciences

Research output: Contribution to journal › Article › peer-review

11 Scopus citations

Abstract

Distributionally robust optimization is a popular modeling paradigm in which the underlying distribution of the random parameters in a stochastic optimization model is unknown. Therefore, hedging against a range of distributions, properly characterized in an ambiguity set, is of interest. We study two-stage stochastic programs with linear recourse in the context of distributional ambiguity, and formulate several distributionally robust models that vary in how the ambiguity set is built. We focus on the Wasserstein distance under a p-norm, and an extension, an optimal quadratic transport distance, as mechanisms to construct the set of probability distributions, allowing the support of the random variables to be a continuous space. We study both unbounded and bounded support sets, and provide guidance regarding which models are meaningful in the sense of yielding robust first-stage decisions. We develop cutting-plane algorithms to solve two classes of problems, and test them on a supply-allocation problem. Our numerical experiments provide further evidence as to what type of problems benefit the most from a distributionally robust solution.

Original language	English (US)
Pages (from-to)	1499-1522
Number of pages	24
Journal	SIAM Journal on Optimization
Volume	32
Issue number	3
DOIs	https://doi.org/10.1137/20M1370227
State	Published - 2022

Funding

\ast Received by the editors June 17, 2020; accepted for publication (in revised form) March 31, 2022; published electronically July 7, 2022. A preliminary version of this paper appeared in Proceedings of the 52nd Annual ACM Symposium on Theory of Computing, 2020. https://doi.org/10.1137/20M1346286 Funding: This research was done under the auspices of the Indo-US Virtual Networked Joint Center IUSSTF/JC-017/2017. The first author was supported in part by NSF award CCF-1907820. The third author was supported in part by NSF award CCF-1535972 and NSF CAREER award CCF-1750140. \dagger Computer Science Department, Carnegie Mellon University, Pittsburgh, PA 15213 USA ([email protected]). \ddagger Department of Computer Science and Engineering, IIT Delhi, New Delhi, India (amitk@ cse.iitd.ac.in). \S Department of Computer Science, Duke University, Durham, NC 27708 USA (debmalya@ cs.duke.edu).

Keywords

Wasserstein distance
distributionally robust optimization
optimal transport distance
two-stage stochastic programming

ASJC Scopus subject areas

Software
Theoretical Computer Science
Applied Mathematics

Access to Document

10.1137/20M1370227

Cite this

@article{759ba4d01d584edea79941bc928da157,

title = "DISTRIBUTIONALLY ROBUST TWO-STAGE STOCHASTIC PROGRAMMING",

abstract = "Distributionally robust optimization is a popular modeling paradigm in which the underlying distribution of the random parameters in a stochastic optimization model is unknown. Therefore, hedging against a range of distributions, properly characterized in an ambiguity set, is of interest. We study two-stage stochastic programs with linear recourse in the context of distributional ambiguity, and formulate several distributionally robust models that vary in how the ambiguity set is built. We focus on the Wasserstein distance under a p-norm, and an extension, an optimal quadratic transport distance, as mechanisms to construct the set of probability distributions, allowing the support of the random variables to be a continuous space. We study both unbounded and bounded support sets, and provide guidance regarding which models are meaningful in the sense of yielding robust first-stage decisions. We develop cutting-plane algorithms to solve two classes of problems, and test them on a supply-allocation problem. Our numerical experiments provide further evidence as to what type of problems benefit the most from a distributionally robust solution.",

keywords = "Wasserstein distance, distributionally robust optimization, optimal transport distance, two-stage stochastic programming",

author = "Daniel Duque and Sanjay Mehrotra and MORTON, {DAVID P.}",

note = "Publisher Copyright: {\textcopyright} 2022 Society for Industrial and Applied Mathematics.",

year = "2022",

doi = "10.1137/20M1370227",

language = "English (US)",

volume = "32",

pages = "1499--1522",

journal = "SIAM Journal on Optimization",

issn = "1052-6234",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - DISTRIBUTIONALLY ROBUST TWO-STAGE STOCHASTIC PROGRAMMING

AU - Duque, Daniel

AU - Mehrotra, Sanjay

AU - MORTON, DAVID P.

PY - 2022

Y1 - 2022

N2 - Distributionally robust optimization is a popular modeling paradigm in which the underlying distribution of the random parameters in a stochastic optimization model is unknown. Therefore, hedging against a range of distributions, properly characterized in an ambiguity set, is of interest. We study two-stage stochastic programs with linear recourse in the context of distributional ambiguity, and formulate several distributionally robust models that vary in how the ambiguity set is built. We focus on the Wasserstein distance under a p-norm, and an extension, an optimal quadratic transport distance, as mechanisms to construct the set of probability distributions, allowing the support of the random variables to be a continuous space. We study both unbounded and bounded support sets, and provide guidance regarding which models are meaningful in the sense of yielding robust first-stage decisions. We develop cutting-plane algorithms to solve two classes of problems, and test them on a supply-allocation problem. Our numerical experiments provide further evidence as to what type of problems benefit the most from a distributionally robust solution.

AB - Distributionally robust optimization is a popular modeling paradigm in which the underlying distribution of the random parameters in a stochastic optimization model is unknown. Therefore, hedging against a range of distributions, properly characterized in an ambiguity set, is of interest. We study two-stage stochastic programs with linear recourse in the context of distributional ambiguity, and formulate several distributionally robust models that vary in how the ambiguity set is built. We focus on the Wasserstein distance under a p-norm, and an extension, an optimal quadratic transport distance, as mechanisms to construct the set of probability distributions, allowing the support of the random variables to be a continuous space. We study both unbounded and bounded support sets, and provide guidance regarding which models are meaningful in the sense of yielding robust first-stage decisions. We develop cutting-plane algorithms to solve two classes of problems, and test them on a supply-allocation problem. Our numerical experiments provide further evidence as to what type of problems benefit the most from a distributionally robust solution.

KW - Wasserstein distance

KW - distributionally robust optimization

KW - optimal transport distance

KW - two-stage stochastic programming

UR - http://www.scopus.com/inward/record.url?scp=85136598025&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85136598025&partnerID=8YFLogxK

U2 - 10.1137/20M1370227

DO - 10.1137/20M1370227

M3 - Article

AN - SCOPUS:85136598025

SN - 1052-6234

VL - 32

SP - 1499

EP - 1522

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

IS - 3

ER -

DISTRIBUTIONALLY ROBUST TWO-STAGE STOCHASTIC PROGRAMMING

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this