Creator of Knowledge
Information Resources Management Association
Advancing the Concepts & Practices of Information Resources Management in Modern Organizations

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

Scatter Search and Path Relinking: A Tutorial on the Linear Arrangement Problem
View Sample PDF
Author(s): 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) and Fred Glover (OptTek Systems, Inc., USA)
Copyright: 2013
Pages: 21
Source title: Recent Algorithms and Applications in Swarm Intelligence Research
Source Author(s)/Editor(s): Yuhui Shi (Southern University of Science and Technology (SUSTech), China)
DOI: 10.4018/978-1-4666-2479-5.ch001


View Scatter Search and Path Relinking: A Tutorial on the Linear Arrangement Problem on the publisher's website for pricing and purchasing information.


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.

Related Content

Rafael Martí, Juan-José Pantrigo, Abraham Duarte, Vicente Campos, Fred Glover. © 2013. 21 pages.
Peng-Yeng Yin, Fred Glover, Manuel Laguna, Jia-Xian Zhu. © 2013. 20 pages.
Volodymyr P. Shylo, Oleg V. Shylo. © 2013. 10 pages.
Tabitha James, Cesar Rego. © 2013. 19 pages.
Gary G. Yen, Wen-Fung Leong. © 2013. 25 pages.
Shi Cheng, Yuhui Shi, Quande Qin. © 2013. 29 pages.
Xin-She Yang. © 2013. 12 pages.
Body Bottom