- Title
- Incremental network design with maximum flows
- Creator
- Kalinowski, Thomas; Matsypura, Dmytro; Savelsbergh, Martin W. P.
- Relation
- European Journal of Operational Research Vol. 242, Issue 1, p. 51-62
- Publisher Link
- http://dx.doi.org/10.1016/j.ejor.2014.10.003
- Publisher
- Elsevier
- Resource Type
- journal article
- Date
- 2015
- Description
- 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.
- Subject
- network design; approximation algorithms; scheduling
- Identifier
- http://hdl.handle.net/1959.13/1332466
- Identifier
- uon:26872
- Identifier
- ISSN:0377-2217
- Rights
- © 2015. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
- Language
- eng
- Full Text
- Reviewed
- Hits: 1812
- Visitors: 2612
- Downloads: 624
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT02 | Author final version | 551 KB | Adobe Acrobat PDF | View Details Download |