Algorithms for the minimum spanning tree problem with resource allocation. (2016)

• Record Type: Journal Article
• Authors: Kataoka, Seiji; Yamada, Takeo
• Is Part Of: Operations research perspectives. Volume 3(2016)
• Page Start: 5
• Page End: 13
• Publication Date: 2016
• Subjects: Minimum spanning tree problem -- Resource allocation -- Trade-off analysis -- Branch-and-bound method; Operations research -- Periodicals; Management science -- Periodicals; 658.403405
• DOI: 10.1016/j.orp.2015.12.001
• Languages: English
• ISSNs: 2214-7160

Abstract

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 N P -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 - fractional solution, 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.