Optimization Online


Incremental Network Design with Maximum Flows

Thomas Kalinowski(thomas.kalinowski***at***newcastle.edu.au)
Dmytro Matsypura(dmytro.matsypura***at***sydney.edu.au)
Martin W.P. Savelsbergh(martin.savelsbergh***at***newcastle.edu.au)

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, and we find small instances for which the heuristics fail to find an optimal solution.

Keywords: network design, approximation algorithms, scheduling

Category 1: Network Optimization

Category 2: Combinatorial Optimization (Approximation Algorithms )


Download: [PDF]

Entry Submitted: 12/22/2013
Entry Accepted: 01/01/2014
Entry Last Modified: 12/22/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society