Incremental Network Design with Maximum Flows

Abstract

We study an incremental network design problem, where in each time period of the planning horizon an arc can be added to the network and a maximum flow problem is solved, and where the objective is to maximize the cumulative flow over the entire planning horizon. After presenting two mixed integer programming (MIP) formulations for this NP-complete problem, we describe several heuristics and prove performance bounds for some special cases. In a series of computational experiments, we compare the performance of the MIP formulations as well as the heuristics.

26 pages

Cited by in corpus (4)

• PowerModelsRestoration.jl: An Open-Source Framework for Exploring Power Network Restoration Algorithms
• The State-of-the-Art Survey on Optimization Methods for Cyber-physical Networks
• Scheduling arc shut downs in a network to maximize flow over time with a bounded number of jobs per time period
• Multi-period Stochastic Network Design for Combined Natural Gas and Hydrogen Distribution