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...
Ergebnis 5 von 5

Details

Autor(en) / Beteiligte
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

Weiterführende Literatur

Empfehlungen zum selben Thema automatisch vorgeschlagen von bX