Article ID: | iaor20134048 |
Volume: | 56 |
Issue: | 3 |
Start Page Number: | 1029 |
End Page Number: | 1043 |
Publication Date: | Jul 2013 |
Journal: | Journal of Global Optimization |
Authors: | Butenko Sergiy, Prokopyev Oleg, Ursulenko Oleksii |
Keywords: | global optimization, minimum spanning trees |
This paper studies the sum‐of‐ratios version of the classical minimum spanning tree problem. We describe a branch‐and‐bound algorithm for solving the general version of the problem based on its image space representation. The suggested approach specifically addresses the difficulties arising in the case when the number of ratios exceeds two. The efficacy of our approach is demonstrated on randomly generated complete and sparse graph instances.