Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
476034 | Computers & Operations Research | 2008 | 14 Pages |
In this paper we discuss models and methods for solving the rooted distance constrained minimum spanning tree problem which is defined as follows: given a graph G=(V,E)G=(V,E) with node set V={0,1,…,n}V={0,1,…,n} and edge set EE, two integer weights, a cost cece and a delay wewe associated with each edge ee of EE, and a natural (time limit) number HH, we wish to find a spanning tree TT of the graph with minimum total cost and such that the unique path from a specified root node, node 0, to any other node has total delay not greater than HH. This problem generalizes the well known hop-constrained spanning tree problem and arises in the design of centralized networks with quality of service constraints and also in package shipment with service guarantee constraints. We present three theoretically equivalent modeling approaches, a column generation scheme, a Lagrangian relaxation combined with subgradient optimization procedure, both based on a path formulation of the problem, and a shortest path (compact) reformulation of the problem which views the underlying subproblem as defined in a layered extended graph. We present results for complete graph instances with up to 40 nodes. Our results indicate that the layered graph path reformulation model is still quite good when the arc weights are reasonably small. Lagrangian relaxation combined with subgradient optimization procedure appears to work much better than column generation and seems to be a quite reasonable approach to the problem for large weight, and even small weight, instances.