Scatter Search and Path Relinking: A Tutorial on the Linear Arrangement Problem

Rafael Martí, Juan-José Pantrigo, Abraham Duarte, Vicente Campos and Fred Glover
Additional contact information
Rafael Martí: Universidad de Valencia, Spain
Juan-José Pantrigo: Universidad Rey Juan Carlos, Spain
Abraham Duarte: Universidad Rey Juan Carlos, Spain
Vicente Campos: Universidad de Valencia, Spain
Fred Glover: OptTek Systems, Inc., USA

International Journal of Swarm Intelligence Research (IJSIR), 2011, vol. 2, issue 2, 1-21

Abstract: Scatter search (SS) and path relinking (PR) are evolutionary methods that have been successfully applied to a wide range of hard optimization problems. The fundamental concepts and principles of the methods were first proposed in the 1970s and 1980s, and were based on formulations, dating back to the 1960s, for combining decision rules and problem constraints. The methods use strategies for search diversification and intensification that have proved effective in a variety of optimization problems and that have sometimes been embedded in other evolutionary methods to yield improved performance. This paper examines the scatter search and path relinking methodologies from both conceptual and practical points of view, and identifies certain connections between their strategies and those adopted more recently by particle swarm optimization. The authors describe key elements of the SS & PR approaches and apply them to a hard combinatorial optimization problem: the minimum linear arrangement problem, which has been used in applications of structural engineering, VLSI and software testing.

Date: 2011
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 4018/jsir.2011040101 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:jsir00:v:2:y:2011:i:2:p:1-21

Access Statistics for this article

International Journal of Swarm Intelligence Research (IJSIR) is currently edited by Yuhui Shi

More articles in International Journal of Swarm Intelligence Research (IJSIR) from IGI Global
Bibliographic data for series maintained by Journal Editor ().