.png){kind=icon}
Return
RAMP for the capacitated minimum spanning tree problem
.png){kind=icon}
PRE
AI
DOI：10.1007/s10479-010-0800-4.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Minimum spanning tree
Heuristics
Surrogate constraints
Scatter search
Tabu search
RAMP
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
4.5
Papers:
8.1K
Citations:
2.1W
Organization
Cited Papers
.png){kind=icon}
ShareSaveShareSave
View more