Abstract
In this paper we discuss formulations for the Two Level Network Design (TLND) problem. In particular, we present an arborescence based formulation with extra constraints guaranteeing that the set of primary nodes is spanned by primary edges. This characterization suggests an arborescence based Lagrangian relaxation where the extra constraints are dualized. Although the Linear Programming (LP) value of the new formulation is proved to be theoretically weaker than the LP bound given by the flow based formulation presented by Balakrishnan, Magnanti and Mirchandani, our computational results show that for certain classes of instances the two LP bounds are quite close. Our results also show that the Lagrangian relaxation based method is quite efficient, providing a reasonable alternative to handle the problem.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R. Ahuja, T. Magnanti and J. Orlin, Network Flow: Theory, Algorithms and Applications (Prentice–Hall, Englewood Cliffs, NJ, 1993).
A. Balakrishnan, T. Magnanti and P. Mirchandani, Modeling and heuristic worst–case performance analysis of the two–level network design problem, Management Science 40(7) (1994) 846–867.
A. Balakrishnan, T. Magnanti and P. Mirchandani, Dual–based algorithm for multi–level network design, Management Science 40(5) (1994) 567–581.
J.R. Current, C.S. Revelle and J.L. Cohon, The hierarchical network design problem, European Journal of Operational Research 27 (1986) 57–66.
C. Duin and T. Volgenant, The multi–weighted Steiner tree problem, Annals of Operations Research 33 (1991) 451–469.
M. Fischetti, and P. Toth, An efficient algorithm for the min–sum arborescence problem on complete digraphs, ORSA Journal on Computing 5(4) (1993) 426–434.
M. Goemans and Y. Myung, A catalog of Steiner tree formulations, Networks 23 (1993) 19–28.
M. Held, P. Wolfe, and H.P. Crowder, Validation of subgradient optimization, Mathematical Programming 6 (1974) 62–88.
F.W. Hwang and D.S. Richards, Steiner tree problems, Networks 22 (1992) 55–90.
B.N. Khoury, P.M. Pardalos and D.W. Hearn, Equivalent formulations for the Steiner problem in graphs, in: Network Optimization Problems, eds. D.–Z. Du and P.M. Pardalos (1993) pp. 111–123.
T.L. Magnanti and L.A. Wolsey, Optimal trees, in: Handbooks in OR & MS, Vol. 7, eds. M.O. Ball et al. (1995) pp. 503–615.
S. Voss, Steiner Probleme in Graphen, Mathematical Systems in Economics (1990).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Gouveia, L., Telhada, J. An Augmented Arborescence Formulation for the Two-Level Network Design Problem. Annals of Operations Research 106, 47–61 (2001). https://doi.org/10.1023/A:1014553523631
Issue Date:
DOI: https://doi.org/10.1023/A:1014553523631