Journal
MATHEMATICAL PROGRAMMING
Volume 196, Issue 1-2, Pages 641-672Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s10107-020-01605-y
Keywords
Distributionally robust; Chance constraints; Mixing sets; Wasserstein ambiguity
Categories
Funding
- ONR [N00014-19-1-2321]
- Institute for Basic Science [IBS-R029-C1]
- DARPA Lagrange Program [N660011824020]
- NSF [1740707]
Ask authors/readers for more resources
This study focuses on enhancing existing mixed-integer programming formulations for distributionally robust chance-constrained programs with random right-hand sides over Wasserstein ambiguity sets. By revealing connections and providing improved formulations, the research shows significant reductions in overall solution times, enabling larger problem sizes to be handled effectively in practical applications.
We consider exact deterministic mixed-integer programming (MIP) reformulations of distributionally robust chance-constrained programs (DR-CCP) with random right-hand sides over Wasserstein ambiguity sets. The existing MIP formulations are known to have weak continuous relaxation bounds, and, consequently, for hard instances with small radius, or with large problem sizes, the branch-and-bound based solution processes suffer from large optimality gaps even after hours of computation time. This significantly hinders the practical application of the DR-CCP paradigm. Motivated by these challenges, we conduct a polyhedral study to strengthen these formulations. We reveal several hidden connections between DR-CCP and its nominal counterpart (the sample average approximation), mixing sets, and robust 0-1 programming. By exploiting these connections in combination, we provide an improved formulation and two classes of valid inequalities for DR-CCP. We test the impact of our results on a stochastic transportation problem numerically. Our experiments demonstrate the effectiveness of our approach; in particular our improved formulation and proposed valid inequalities reduce the overall solution times remarkably. Moreover, this allows us to significantly scale up the problem sizes that can be handled in such DR-CCP formulations by reducing the solution times from hours to seconds.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available