![The capacitated minimum spanning tree problem: On improved multistar constraints [An article from: European Journal of Operational Research]](https://www.ebooknetworking.net/books/B00/0RR/bigB000RR2PCM.jpg)
The capacitated minimum spanning tree problem: On improved multistar constraints [An article from: European Journal of Operational Research]
Book Details
Author(s)L. Gouveia, M. Joao Lopes
PublisherElsevier
ISBN / ASINB000RR2PCM
ISBN-13978B000RR2PC6
MarketplaceFrance 🇫🇷
Description
This digital document is a journal article from European Journal of Operational Research, published by Elsevier in 2005. The article is delivered in HTML format and is available in your Amazon.com Media Library immediately after purchase. You can view it with any web browser.
Description:
In this paper, we propose a new set of valid inequalities for the Capacitated Minimum Spanning Tree (CMST) problem with general node demands. These inequalities are stronger versions of the well-known multistar constraints (see Hall [Informs J. Comput. 8 (1996) 219]). We also propose and test one lagrangean relaxation scheme that dualizes the new constraints. Our computational results involving instances with up to 80 nodes plus the root node, show that the new inequalities are worth using for random cost and sparse instances. These instances appear to be more difficult to solve than Euclidean ones. We also propose a new arc elimination test for the CMST problem. Besides helping to reduce the size of the instances being solved, the new test improves the performance of the lagrangean relaxation proposed in this paper for the random cost instances.
Description:
In this paper, we propose a new set of valid inequalities for the Capacitated Minimum Spanning Tree (CMST) problem with general node demands. These inequalities are stronger versions of the well-known multistar constraints (see Hall [Informs J. Comput. 8 (1996) 219]). We also propose and test one lagrangean relaxation scheme that dualizes the new constraints. Our computational results involving instances with up to 80 nodes plus the root node, show that the new inequalities are worth using for random cost and sparse instances. These instances appear to be more difficult to solve than Euclidean ones. We also propose a new arc elimination test for the CMST problem. Besides helping to reduce the size of the instances being solved, the new test improves the performance of the lagrangean relaxation proposed in this paper for the random cost instances.
