The Capacitated Minimal Spanning Tree Problem: An experiment with a hop‐indexedmodel

L. Gouveia and P. Martins

Annals of Operations Research, 1999, vol. 86, issue 0, 294 pages

Abstract: The Capacitated Minimal Spanning Tree Problem (CMSTP) is to find a minimal spanningtree with an additional cardinality constraint on the size of the subtrees off of a given rootnode. This problem is closely related to the design of centralized networks where one wantsto link, with minimum cost, several terminals to a given root node (typically, a concentratoror a computer center). In this paper, we present a new extended and compact formulationfor the CMSTP. This formulation is a “hop‐indexed” single‐commodity flow model andgeneralizes a well‐known single‐commodity flow model. We introduce a new set of validinequalities, denoted by “hop ordering” inequalities, which are not redundant for the LPrelaxation of the new formulation. We present a new cutting plane method for the CMSTPwith the new formulation as the initial model and using constraint generation for adding“hop‐ordering” constraints and generalized subtour elimination constraints to the currentLP model. We present computational results from a set of tests with 40 and 80 nodes whichcompare our lower bounds with the bounds given by other known methods. The main contributionof our proposed method is to considerably close previously known gaps for testswhich have been classified as hard ones, namely tightly capacitated tests with the root in thecorner of the grid of points. Copyright Kluwer Academic Publishers 1999

Date: 1999
References: Add references at CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018911003529 (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:86:y:1999:i:0:p:271-294:10.1023/a:1018911003529

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

DOI: 10.1023/A:1018911003529

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