Branch-and-cut-and-price algorithms for the Degree Constrained Minimum Spanning Tree Problem

Luis Bicalho (), Alexandre Cunha and Abilio Lucena ()

Computational Optimization and Applications, 2016, vol. 63, issue 3, 755-792

Abstract: Assume that a connected undirected edge weighted graph G is given. The Degree Constrained Minimum Spanning Tree Problem (DCMSTP) asks for a minimum cost spanning tree of G where vertex degrees do not exceed given pre-defined upper bounds. In this paper, three exact solution algorithms are investigated for the problem. All of them are Branch-and-cut based and rely on the strongest formulation currently available for the problem. Additionally, to speed up the computation of dual bounds, they all use column generation, in one way or another. To test the algorithms, new hard to solve DCMSTP instances are proposed here. These instances, combined with additional ones taken from the literature, are then used in computational experiments. The experiments compare the new algorithms among themselves and also against the best algorithms currently available in the literature. As an outcome of them, one of the new algorithms stands out on top. Copyright Springer Science+Business Media New York 2016

Keywords: Degree Constrained Spanning Tree; Branch-and-cut; Branch-and-cut-and-price (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10589-015-9788-7 (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:coopap:v:63:y:2016:i:3:p:755-792

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

DOI: 10.1007/s10589-015-9788-7

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().