V. Campos, M. Laguna, and R. Martí
New Ideas in Optimization, D. Corne, M. Dorigo and F. Glover (Eds.), McGraw-Hill, pp. 331-339 (1999)
Scatter search is a population-based 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, such as the surrogate constraint method, scatter search uses strategies for combining solution vectors that have proved effective in a variety of problem settings. In this paper, we present a scatter search implementation designed to find high quality solutions for the linear ordering problem. This NP-hard problem has a significant number of applications in practice. The LOP, for example, is equivalent to the so-called triangulation problem for input-output tables in economics. Our implementation goes beyond a simple exercise on applying scatter search, since it incorporates innovative mechanisms to combine solutions and to create a balance between quality and diversification in the reference set. Extensive computational experiments with input-output tables are used to assess the merit of our procedure.
Full text
