Solving Network Design Problems via Iterative Aggregation

Beitrag in einer Fachzeitschrift
(Originalarbeit)


Details zur Publikation

Autorinnen und Autoren: Bärmann A, Liers F, Martin A, Merkert M, Thurner C, Weninger D
Titel Sammelwerk: Mathematical Programming Computation
Zeitschrift: Mathematical Programming Computation
Verlagsort: Heidelberg
Jahr der Veröffentlichung: 2015
Band: 7
Heftnummer: 2
Seitenbereich: 189-217
ISSN: 1867-2957
Sprache: Englisch


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 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.



FAU-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Bärmann, Andreas Dr.
Lehrstuhl für Angewandte Mathematik (Gemischt-ganzzahlige lineare und nichtlineare Optimierung)
Liers-Bergmann, Frauke Prof. Dr.
Professur für Angewandte Mathematik (Ganzzahlige und robuste Optimierung)
Martin, Alexander Prof. Dr.
Lehrstuhl für Angewandte Mathematik (Gemischt-ganzzahlige lineare und nichtlineare Optimierung)
Merkert, Maximilian
Lehrstuhl für Angewandte Mathematik (Gemischt-ganzzahlige lineare und nichtlineare Optimierung)
Thurner, Christoph Dr.
Lehrstuhl für Angewandte Mathematik (Gemischt-ganzzahlige lineare und nichtlineare Optimierung)
Weninger, Dieter Dr.
Lehrstuhl für Angewandte Mathematik (Gemischt-ganzzahlige lineare und nichtlineare Optimierung)


Zusätzliche Organisationseinheit(en)
Lehrstuhl für Angewandte Mathematik (Gemischt-ganzzahlige lineare und nichtlineare Optimierung)


Zitierweisen

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), 189-217. https://dx.doi.org/10.1007/s12532-015-0079-1

MLA:
Bärmann, Andreas, et al. "Solving Network Design Problems via Iterative Aggregation." Mathematical Programming Computation 7.2 (2015): 189-217.

BibTeX: 

Zuletzt aktualisiert 2018-19-07 um 16:31