کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
475279 | 699275 | 2010 | 11 صفحه PDF | دانلود رایگان |
Given an undirected network with positive edge costs and a positive integer d>2d>2, the minimum-degree constrained minimum spanning tree problem is the problem of finding a spanning tree with minimum total cost such that each non-leaf node in the tree has a degree of at least dd. This problem is new to the literature while the related problem with upper bound constraints on degrees is well studied. Mixed-integer programs proposed for either type of problem is composed, in general, of a tree-defining part and a degree-enforcing part. In our formulation of the minimum-degree constrained minimum spanning tree problem, the tree-defining part is based on the Miller–Tucker–Zemlin constraints while the only earlier paper available in the literature on this problem uses single and multi-commodity flow-based formulations that are well studied for the case of upper degree constraints. We propose a new set of constraints for the degree-enforcing part that lead to significantly better solution times than earlier approaches when used in conjunction with Miller–Tucker–Zemlin constraints.
Journal: Computers & Operations Research - Volume 37, Issue 1, January 2010, Pages 72–82