Article ID: | iaor20108925 |
Volume: | 181 |
Issue: | 1 |
Start Page Number: | 661 |
End Page Number: | 681 |
Publication Date: | Dec 2010 |
Journal: | Annals of Operations Research |
Authors: | Glover Fred, Rego Cesar, Mathew Frank |
Keywords: | cutting plane algorithms, minimum spanning trees |
This paper introduces dual and primal-dual RAMP algorithms for the solution of the capacitated minimum spanning tree problem (CMST). A surrogate constraint relaxation incorporating cutting planes is proposed to explore the dual solution space. In the dual RAMP approach, primal-feasible solutions are obtained by simple tabu searches that project dual solutions onto primal feasible space. A primal-dual approach is achieved by including a scatter search procedure that further exploits the adaptive memory framework. Computational results from applying the methods to a standard set of benchmark problems disclose that the dual RAMP algorithm finds high quality solutions very efficiently and that its primal-dual enhancement is still more effective.