Constraint Generation for Two-Stage Robust Network Flow Problems
INFORMS Journal on Optimization · 2019
DOI: 10.1287/ijoo.2018.0003 ↗Kurz gefasst
Fachartikel in der Zeitschrift INFORMS Journal on Optimization, 2019. Verfasst von David Simchi-Levi und 2 weiteren Autor:innen. Die Arbeit wurde bisher 42-mal zitiert (Crossref) und nennt 39 Literaturangaben.
Abstract (Originalsprache)
In this paper, we propose new constraint generation (CG) algorithms for solving the two-stage robust minimum cost flow problem, a problem that arises from various applications such as transportation and logistics. To develop efficient algorithms under general polyhedral uncertainty sets, we repeatedly exploit the network-flow structure to reformulate the two-stage robust minimum cost flow problem as a single-stage optimization problem. The reformulation gives rise to a natural CG algorithm and, more importantly, leads to a method for solving the separation problem using a pair of mixed integer linear programs (MILPs). We then propose another algorithm by combining our MILP-based method with the column-and-constraint generation (C&CG) framework proposed by Zeng and Zhao . We establish convergence guarantees for both CG and C&CG algorithms. In computational experiments, we show that both algorithms are effective at solving two-stage robust minimum cost flow problems with hundreds of nodes.
Zitieren
APA
Simchi-Levi, D., Wang, H., & Wei, Y. (2019). Constraint Generation for Two-Stage Robust Network Flow Problems. INFORMS Journal on Optimization. https://doi.org/10.1287/ijoo.2018.0003
Vancouver
Simchi-Levi D, Wang H, Wei Y. Constraint Generation for Two-Stage Robust Network Flow Problems. INFORMS Journal on Optimization. 2019. doi:10.1287/ijoo.2018.0003
BibTeX
@article{SimchiLevi2019,
author = {Simchi-Levi, David and Wang, He and Wei, Yehua},
title = {Constraint Generation for Two-Stage Robust Network Flow Problems},
journal = {INFORMS Journal on Optimization},
year = {2019},
doi = {10.1287/ijoo.2018.0003}
}
EUVIMED