Kalinowski, Thomas; Matsypura, Dmytro; Savelsbergh, Martin W P

Author(s)

Kalinowski, Thomas

Matsypura, Dmytro

Savelsbergh, Martin W P

Publication Date

2015-04-01

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.

Citation

European Journal of Operational Research, 242(1), p. 51-62

ISSN

1872-6860

0377-2217

Link

https://hdl.handle.net/1959.11/26776

Publisher

Elsevier BV

Title

Incremental network design with maximum flows

Type of document

Journal Article

Entity Type

Publication

Author(s)	Kalinowski, Thomas Matsypura, Dmytro Savelsbergh, Martin W P
Publication Date	2015-04-01
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.
Citation	European Journal of Operational Research, 242(1), p. 51-62
ISSN	1872-6860 0377-2217
Link	https://hdl.handle.net/1959.11/26776
Publisher	Elsevier BV
Title	Incremental network design with maximum flows
Type of document	Journal Article
Entity Type	Publication

Incremental network design with maximum flows

Files: