An experimental evaluation of a scatter search for the linear ordering problem

Scatter search is a population-based method that has recently been shown to yield promising outcomes for solving combinatorial and nonlinear global op timization problems. Based on formulations originally proposed in the 1960s for combining decision rules and problem constraints, such as in generatin g surrogate constraints, scatter search uses strategies for combining solut ion vectors that have proved effective in a variety of problem settings. In this paper, we present a scatter search implementation designed to find hi gh quality solutions for the NP-hard linear ordering problem, which has a s ignificant number of applications in practice. The LOP, for example, is equ ivalent to the so-called triangulation problem for input-output tables in e conomics. Our implementation incorporates innovative mechanisms to combine solutions and to create a balance between quality and diversification in th e reference set. We also use a tracking process that generates solution sta tistics disclosing the nature of combinations and the ranks of antecedent s olutions that produced the best final solutions. Extensive computational ex periments with more than 300 instances establishes the effectiveness of our procedure in relation to approaches previously identified to be best.