An Augmented Arborescence Formulation for the Two-Level Network Design Problem

Luis Gouveia () and João Telhada ()

Annals of Operations Research, 2001, vol. 106, issue 1, 47-61

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. Copyright Kluwer Academic Publishers 2001

Keywords: network design; spanning trees and steiner trees; multicommodity flow models; linear programming relaxations (search for similar items in EconPapers)
Date: 2001
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1014553523631 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:106:y:2001:i:1:p:47-61:10.1023/a:1014553523631

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1014553523631

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().