کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9664100 | 1446257 | 2005 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The capacitated minimum spanning tree problem: On improved multistar constraints
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: The capacitated minimum spanning tree problem: On improved multistar constraints The capacitated minimum spanning tree problem: On improved multistar constraints](/preview/png/9664100.png)
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 160, Issue 1, 1 January 2005, Pages 47-62
Journal: European Journal of Operational Research - Volume 160, Issue 1, 1 January 2005, Pages 47-62
نویسندگان
LuıÌs Gouveia, Maria João Lopes,