Scatter Search

Manuel Laguna

ABSTRACT

This article explores the metaheuristic approach called scatter search, which is an evolutionary method that has recently been shown to yield promising outcomes for solving combinatorial and nonlinear optimization problems. Based on formulations originally proposed in the 1960s for combining decision rules and problem constraints, this method uses strategies for combining solution vectors that have proved effective in a variety of problem areas. Scatter search can be implemented in multiple ways, and offers numerous alternatives for exploiting its fundamental ideas. We identify a general design and illustrate the main features in the context of a classical integer programming problem.