  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.
