Incremental network design with maximum flows

•An incremental network design problem is studied, where the objective is to maximize the cumulative s-t-flow over a time horizon.•Two mixed integer programming (MIP) formulations are presented.•Two greedy heuristics are described and performance guarantees in special cases are proved.•The MIP formu...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2015-04, Vol.242 (1), p.51-62
Main Authors: Kalinowski, Thomas, Matsypura, Dmytro, Savelsbergh, Martin W.P.
Format: Article
Language:English
Subjects:
Approximation algorithms
Computation
Formulations
Heuristic
Incremental networks
Integer programming
Linear programming
Network design
Network flow problem
Networks
Operational research
Operations research
Process planning
Scheduling
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•An incremental network design problem is studied, where the objective is to maximize the cumulative s-t-flow over a time horizon.•Two mixed integer programming (MIP) formulations are presented.•Two greedy heuristics are described and performance guarantees in special cases are proved.•The MIP formulations as well as the heuristics are compared in computational experiments on randomly generated instances. 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.
ISSN:0377-2217
1872-6860
DOI:10.1016/j.ejor.2014.10.003