A data-driven distributionally robust bound on the expected optimal value of uncertain mixed 0-1 linear programming
From MaRDI portal
Publication:1789641
DOI10.1007/S10287-018-0298-9zbMATH Open1397.90272arXiv1708.07603OpenAlexW2746085324MaRDI QIDQ1789641FDOQ1789641
Authors: Guanglin Xu, Samuel Burer 
Publication date: 10 October 2018
Published in: Computational Management Science (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1708.07603
Recommendations
- Distributionally robust optimization under moment uncertainty with application to data-driven problems
- Linear programming with uncertain data: some extensions to robust optimization
- On distributionally robust chance-constrained linear programs
- Mixed 0-1 Linear Programs Under Objective Uncertainty: A Completely Positive Representation
- scientific article; zbMATH DE number 7708787
- New robust optimization counterpart for linear optimization with uncertain data
- Robust solutions to multi-objective linear programs with uncertain data
- Distributionally Robust Linear and Discrete Optimization with Marginals
- Data-driven stochastic programming with distributionally robust constraints under Wasserstein distance: asymptotic properties
- A distributionally robust perspective on uncertainty quantification and chance constrained programming
Wasserstein metricsemidefinite programmingcopositive programmingdistributionally robust optimization
Approximation methods and heuristics in mathematical programming (90C59) Semidefinite programming (90C22) Boolean programming (90C09)
Cites Work
- The earth mover's distance as a metric for image retrieval
- Title not available (Why is that?)
- The ellipsoid method and its consequences in combinatorial optimization
- Distributionally robust joint chance constraints with second-order moment information
- On distributionally robust chance-constrained linear programs
- On the copositive representation of binary and continuous nonconvex quadratic programs
- Ambiguous chance constrained problems and robust optimization
- The \(\zeta(2)\) limit in the random assignment problem
- On duality theory of conic linear problems.
- Distributionally robust optimization under moment uncertainty with application to data-driven problems
- Persistency model and its applications in choice modeling
- Generalized Chebyshev Bounds via Semidefinite Programming
- Optimal Inequalities in Probability Theory: A Convex Optimization Approach
- On Cones of Nonnegative Quadratic Functions
- Title not available (Why is that?)
- Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming
- Worst-Case Value-At-Risk and Robust Portfolio Optimization: A Conic Programming Approach
- Data-driven chance constrained stochastic program
- Persistence in discrete optimization under data uncertainty
- Mixed 0-1 Linear Programs Under Objective Uncertainty: A Completely Positive Representation
- Bounding the Project Completion Time Distribution in PERT Networks
- Probabilistic Combinatorial Optimization: Moments, Semidefinite Programming, and Asymptotic Bounds
- The minimax approach to stochastic programming and an illustrative application
- Efficient Estimation of Arc Criticalities in Stochastic Activity Networks
- A gentle, geometric introduction to copositive optimization
- Copositive programming
- Representing quadratically constrained quadratic programs as generalized copositive programs
- Title not available (Why is that?)
- Data-driven robust optimization
- Distributionally robust multi-item newsvendor problems with multimodal demand distributions
- Title not available (Why is that?)
- Ambiguity in portfolio selection
- On reduced semidefinite programs for second order moment bounds with applications
- Distributionally Robust Convex Optimization
- Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations
- Ambiguous joint chance constraints under mean and dispersion information
Cited In (3)
Uses Software
This page was built for publication: A data-driven distributionally robust bound on the expected optimal value of uncertain mixed 0-1 linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1789641)
