A 2n Constraint Formulation for the Capacitated Minimal Spanning Tree Problem

Luis Gouveia
Additional contact information
Luis Gouveia: Universidade de Lisboa, Lisboa, Portugal

Operations Research, 1995, vol. 43, issue 1, 130-141

Abstract: In this paper we present a new formulation for the Capacitated Minimal Spanning Tree ( CMST ) problem. One advantage of the new formulation is that it is more compact (in the number of constraints) than a well-known formulation. Additionally, we show that the linear programming relaxation of both formulations produces optimal solutions with the same cost. We present a brief discussion concerning valid inequalities for the ( CMST ) which are directly derived from the new formulation. We show that some of the new inequalities are not dominated by some sets of facet-inducing inequalities for the ( CMST ). We derive some Lagrangian relaxation-based methods from the new formulation and present computational evidence showing that reasonable improvements on the original linear programming bounds can be obtained if these methods are strengthened by the use of cutting planes. The reported computational results indicate that one of the methods presented in this paper dominates, in most of the cases, the previous best methods reported in the literature. The most significant improvements are obtained in the instances with the root in the corner.

Keywords: networks/graphs: capacitated tree algorithms; programming; integer: Lagrangian relaxation/cutting planes (search for similar items in EconPapers)
Date: 1995
References: Add references at CitEc
Citations: View citations in EconPapers (21)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.43.1.130 (application/pdf)

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:inm:oropre:v:43:y:1995:i:1:p:130-141

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().