Constraint Generation for Two-Stage Robust Network Flow Problems

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.