Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/178266 
Erscheinungsjahr: 
2016
Quellenangabe: 
[Journal:] Operations Research Perspectives [ISSN:] 2214-7160 [Volume:] 3 [Publisher:] Elsevier [Place:] Amsterdam [Year:] 2016 [Pages:] 5-13
Verlag: 
Elsevier, Amsterdam
Zusammenfassung: 
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.
Schlagwörter: 
Minimum spanning tree problem
Resource allocation
Trade-off analysis
Branch-and-bound method
Persistent Identifier der Erstveröffentlichung: 
Creative-Commons-Lizenz: 
cc-by-nc-nd Logo
Dokumentart: 
Article

Datei(en):
Datei
Größe





Publikationen in EconStor sind urheberrechtlich geschützt.