Solving Network Design Problems via Iterative Aggregation
Journal article
(Original article)
Publication Details
Author(s): Bärmann A, Liers F, Martin A, Merkert M, Thurner C, Weninger D
Title edited volumes: Mathematical Programming Computation
Journal: → Mathematical Programming Computation 
Publishing place: Heidelberg
Publication year: 2015
Volume: 7
Journal issue: 2
Pages range: 189217
ISSN: 18672957
Language: English
Abstract
In this work, we present an exact approach for solving network design problems that is based on an iterative graph aggregation procedure. The scheme allows existing preinstalled capacities. Starting with an initial aggregation, we solve a sequence of network design master problems over increasingly finegrained representations of the original network. In each step, a subproblem is solved that either proves optimality of the solution or gives a directive where to refine the representation of the network in the subsequent iteration. The algorithm terminates with a globally optimal solution to the original problem. Our implementation uses a standard integer programming solver for solving the master problems as well as the subproblems. The computational results on random and realistic instances confirm the profitable use of the iterative aggregation technique. The computing time often reduces drastically when our method is compared to solving the original problem from scratch.
FAU Authors / FAU Editors
   Economics  Discrete Optimization  Mathematics (EDOM) 

 LiersBergmann, Frauke Prof. Dr. 
  Professur für Diskrete Optimierung in den Ingenieurwissenschaften 

 Martin, Alexander Prof. Dr. 
  Economics  Discrete Optimization  Mathematics (EDOM) 

   Economics  Discrete Optimization  Mathematics (EDOM) 

   Economics  Discrete Optimization  Mathematics (EDOM) 

   Economics  Discrete Optimization  Mathematics (EDOM) 

Additional Organisation
→ Economics  Discrete Optimization  Mathematics (EDOM) 

How to cite
APA:  Bärmann, A., Liers, F., Martin, A., Merkert, M., Thurner, C., & Weninger, D. (2015). Solving Network Design Problems via Iterative Aggregation. Mathematical Programming Computation, 7(2), 189217. https://dx.doi.org/10.1007/s1253201500791 
MLA:  Bärmann, Andreas, et al. "Solving Network Design Problems via Iterative Aggregation." Mathematical Programming Computation 7.2 (2015): 189217. 