Exportar Publicação

A publicação pode ser exportada nos seguintes formatos: referência da APA (American Psychological Association), referência do IEEE (Institute of Electrical and Electronics Engineers), BibTeX e RIS.

Exportar Referência (APA) 
Gouveia, L. & Lopes, M. J. (2005). The capacitated minimum spanning tree problem: on improved multistar constraints. European Journal of Operational Research . 160 (1), 47-62
Exportar Referência (IEEE) 
L. Gouveia and M. J. Lopes,  "The capacitated minimum spanning tree problem: on improved multistar constraints", in European Journal of Operational Research , vol. 160, no. 1, pp. 47-62, 2005
Exportar BibTeX 
@article{gouveia2005_1732357520006,
	author = "Gouveia, L. and Lopes, M. J.",
	title = "The capacitated minimum spanning tree problem: on improved multistar constraints",
	journal = "European Journal of Operational Research ",
	year = "2005",
	volume = "160",
	number = "1",
	doi = "10.1016/j.ejor.2003.10.021",
	pages = "47-62",
	url = "http://www.sciencedirect.com/science/article/pii/S0377221703007525?via%3Dihub"
}
Exportar RIS 
TY  - JOUR
TI  - The capacitated minimum spanning tree problem: on improved multistar constraints
T2  - European Journal of Operational Research 
VL  - 160
IS  - 1
AU  - Gouveia, L.
AU  - Lopes, M. J.
PY  - 2005
SP  - 47-62
SN  - 0377-2217
DO  - 10.1016/j.ejor.2003.10.021
UR  - http://www.sciencedirect.com/science/article/pii/S0377221703007525?via%3Dihub
AB  - 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.
ER  -