Constraint Generation for Two-Stage Robust Network Flow Problem
Abstract: In this paper, we propose new constraint generation algorithms for solving the two-stage robust minimum cost flow problem, a problem that arises from various applications such as transportation and logistics. In order to develop efficient algorithms under general polyhedral uncertainty set, 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 constraint generation (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 of Zeng and Zhao (2013). 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.
Keywords: robust optimization, two-stage adaptive optimization, network flows, constraint generation
Category 1: Robust Optimization
Category 2: Network Optimization
Citation: Working Paper, Massachusetts Institute of Technology, 2017/9.
Entry Submitted: 09/25/2017
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|