Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9664100 | European Journal of Operational Research | 2005 | 16 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
LuıÌs Gouveia, Maria João Lopes,