UNIVERSI
TÄ
TS-
BIBLIOTHEK
P
ADERBORN
Anmelden
Menü
Menü
Start
Hilfe
Blog
Weitere Dienste
Neuerwerbungslisten
Fachsystematik Bücher
Erwerbungsvorschlag
Bestellung aus dem Magazin
Fernleihe
Einstellungen
Sprache
Deutsch
Deutsch
Englisch
Farbschema
Hell
Dunkel
Automatisch
Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist
gegebenenfalls
nur via VPN oder Shibboleth (DFN-AAI) möglich.
mehr Informationen...
Universitätsbibliothek
Katalog
Suche
Details
Zur Ergebnisliste
Ergebnis 5 von 5
Datensatz exportieren als...
BibTeX
Stabilizing branch-and-price for constrained tree problems
Networks, 2013-03, Vol.61 (2), p.150-170
Leitner, Markus
Ruthmair, Mario
Raidl, Günther R.
2013
Details
Autor(en) / Beteiligte
Leitner, Markus
Ruthmair, Mario
Raidl, Günther R.
Titel
Stabilizing branch-and-price for constrained tree problems
Ist Teil von
Networks, 2013-03, Vol.61 (2), p.150-170
Ort / Verlag
Hoboken: Wiley Subscription Services, Inc., A Wiley Company
Erscheinungsjahr
2013
Link zum Volltext
Quelle
Wiley Blackwell Single Titles
Beschreibungen/Notizen
We consider a rather generic class of network design problems in which a set or subset of given terminal nodes must be connected to a dedicated root node by simple paths and a variety of resource and/or quality of service constraints must be respected. These extensions of the classical Steiner tree problem on a graph can be well modeled by a path formulation in which individual variables are used for all feasible paths. To solve this formulation in practice, branch‐and‐price is used. It turns out, however, that a naive implementation of column generation suffers strongly from certain degeneracies of the pricing subproblem, leading to excessive running times. After analyzing these computational problems, we propose two methods to accelerate and stabilize column generation by using alternative dual‐optimal solutions. The resulting branch‐and‐price approach is practically tested on the rooted delay‐constrained Steiner tree problem and a quota‐constrained version of it. Results indicate that the proposed methods in general speed‐up the solution process dramatically, far more than a piecewise linear stabilization to which we compare. Furthermore, our branch‐and‐price approach exhibits on most test instances a better performance than a state‐of‐the‐art branch‐and‐cut approach based on layered graphs. As the new stabilization technique utilizing alternative dual‐optimal solutions is generic in the sense that it easily adapts to the inclusion of a large variety of further constraints and different objective functions, the proposed method is highly promising for a large class of network design problems. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013
Sprache
Englisch
Identifikatoren
ISSN: 0028-3045
eISSN: 1097-0037
DOI: 10.1002/net.21484
Titel-ID: cdi_proquest_miscellaneous_1541460229
Format
–
Schlagworte
Applied sciences
,
branch-and-price
,
Exact sciences and technology
,
Flows in networks. Combinatorial problems
,
Graphs
,
integer linear programming
,
Mathematical analysis
,
Mathematical models
,
Mathematical programming
,
network design
,
Networks
,
Operational research and scientific management
,
Operational research. Management science
,
Running
,
Stabilization
,
stabilized column generation
,
Steiner tree
,
Terminals
,
Trees
Weiterführende Literatur
Empfehlungen zum selben Thema automatisch vorgeschlagen von
bX