Algorithms for the minimum spanning tree problem with resource allocation
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2016-01-01
|
| Series: | Operations Research Perspectives |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2214716016000026 |
| _version_ | 1828880855262560256 |
|---|---|
| author | Seiji Kataoka Takeo Yamada |
| author_facet | Seiji Kataoka Takeo Yamada |
| author_sort | Seiji Kataoka |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-13T09:55:48Z |
| format | Article |
| id | doaj.art-de1edf77939e474fb8c68ce66001c33e |
| institution | Directory Open Access Journal |
| issn | 2214-7160 |
| language | English |
| last_indexed | 2024-12-13T09:55:48Z |
| publishDate | 2016-01-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Operations Research Perspectives |
| spelling | doaj.art-de1edf77939e474fb8c68ce66001c33e2022-12-21T23:51:47ZengElsevierOperations Research Perspectives2214-71602016-01-013C51310.1016/j.orp.2015.12.001Algorithms for the minimum spanning tree problem with resource allocationSeiji KataokaTakeo YamadaWe 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.http://www.sciencedirect.com/science/article/pii/S2214716016000026Minimum spanning tree problemResource allocationTrade-off analysisBranch-and-bound method |
| spellingShingle | Seiji Kataoka Takeo Yamada Algorithms for the minimum spanning tree problem with resource allocation Operations Research Perspectives Minimum spanning tree problem Resource allocation Trade-off analysis Branch-and-bound method |
| title | Algorithms for the minimum spanning tree problem with resource allocation |
| title_full | Algorithms for the minimum spanning tree problem with resource allocation |
| title_fullStr | Algorithms for the minimum spanning tree problem with resource allocation |
| title_full_unstemmed | Algorithms for the minimum spanning tree problem with resource allocation |
| title_short | Algorithms for the minimum spanning tree problem with resource allocation |
| title_sort | algorithms for the minimum spanning tree problem with resource allocation |
| topic | Minimum spanning tree problem Resource allocation Trade-off analysis Branch-and-bound method |
| url | http://www.sciencedirect.com/science/article/pii/S2214716016000026 |
| work_keys_str_mv | AT seijikataoka algorithmsfortheminimumspanningtreeproblemwithresourceallocation AT takeoyamada algorithmsfortheminimumspanningtreeproblemwithresourceallocation |