• search hit 83 of 89
Back to Result List

Solving network design problems via iterative aggregation

  • 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 fine-grained 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.

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Andreas Bärmann, Frauke Liers, Alexander Martin, Maximilian Merkert, Christoph Thurner, Dieter Weninger
DOI:https://doi.org/10.1007/s12532-015-0079-1
Parent Title (English):Mathematical Programming Computation
Document Type:Article
Language:English
Date of Publication (online):2015/03/25
Date of first Publication:2015/03/25
Release Date:2016/09/27
Tag:Aggregation; Branch-and-cut; Combinatorial optimization; Mixed-integer programming; Network design
Volume:7
Issue:2
First Page:189
Last Page:217
Institutes:Friedrich-Alexander-Universität Erlangen-Nürnberg
Subprojects:A05
B06
B07