RAMP for the capacitated minimum spanning tree problem

RAMP for the capacitated minimum spanning tree problem

0.00 Avg rating0 Votes
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: , ,
Keywords: cutting plane algorithms, minimum spanning trees
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.