# Incremental Network Design with Maximum Flows

Preprint · Thomas Kalinowski, Dmytro Matsypura, Martin W. P. Savelsbergh

- Archive id: arxiv:1312.6447
- Published: 2013-12-23
- Venue: European Journal of Operational Research 242 (2015), pp. 51-62
- DOI: https://doi.org/10.1016/j.ejor.2014.10.003
- arXiv: https://arxiv.org/abs/1312.6447
- Source URL: https://arxiv.org/abs/1312.6447
- PDF: https://arxiv.org/pdf/1312.6447
- Provenance: arxiv

## 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.