Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/178266 
Year of Publication: 
2016
Citation: 
[Journal:] Operations Research Perspectives [ISSN:] 2214-7160 [Volume:] 3 [Publisher:] Elsevier [Place:] Amsterdam [Year:] 2016 [Pages:] 5-13
Publisher: 
Elsevier, Amsterdam
Abstract: 
We formulate the minimum spanning tree problem with resource allocation (MSTRA) in two ways, as discrete and continuous optimization problems (d-MSTRA/c-MSTRA), prove these to be NP-hard, and present algorithms to solve these problems to optimality. We reformulate d-MSTRA as the knapsack constrained minimum spanning tree problem, and solve this problem using a previously published branch-and-bound algorithm. By applying a ‘peg test', the size of d-MSTRA is (significantly) reduced. To solve c-MSTRA, we introduce the concept of f-fractionalsolution, and prove that an optimal solution can be found within this class of solutions. Based on this fact, as well as conditions for ‘pruning' subproblems, we develop an enumerative algorithm to solve c-MSTRA to optimality. We implement these algorithms in ANSI C programming language and, through extensive numerical tests, evaluate the performance of the developed codes on various types of instances.
Subjects: 
Minimum spanning tree problem
Resource allocation
Trade-off analysis
Branch-and-bound method
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by-nc-nd Logo
Document Type: 
Article

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.