Optimization Online


Distributionally Robust Linear and Discrete Optimization with Marginals

Louis Chen(llchen***at***mit.edu)
Will Ma(willma***at***mit.edu)
Karthik Natarajan(karthik_natarajan***at***sutd.edu.sg)
David Simchi-Levi(dslevi***at***mit.edu)
Zhenzhen Yan(a0109727***at***u.nus.edu)

Abstract: In this paper, we study the class of linear and discrete optimization problems in which the objective coefficients are chosen randomly from a distribution, and the goal is to evaluate robust bounds on the expected optimal value as well as the marginal distribution of the optimal solution. The set of joint distributions is assumed to be specified up to only the marginal distributions. We generalize the primal-dual formulations for this problem from the set of joint distributions with absolutely continuous marginal distributions to arbitrary marginal distributions using techniques from optimal transport theory. While the robust bound is shown to be NP-hard to compute for linear optimization problems, we identify a sufficient condition for polynomial time solvability using extended formulations. This generalizes the known tractability results under marginal information from 0-1 polytopes to a class of integral polytopes and has implications on the solvability of distributionally robust optimization problems in areas such as scheduling which we discuss.

Keywords: Robust Optimization, Discrete Optimization, Optimal Transport

Category 1: Applications -- OR and Management Sciences

Category 2: Combinatorial Optimization (Polyhedra )

Category 3: Integer Programming (0-1 Programming )

Citation: Massachusetts Institute of Technology 77 Massachusetts Avenue Bldg. E40-103, Cambridge, MA 02139 April 9, 2018

Download: [PDF]

Entry Submitted: 04/09/2018
Entry Accepted: 04/09/2018
Entry Last Modified: 04/09/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society