Schiavinotto, Tommaso; Stützle, Thomas The linear ordering problem: instances, search space analysis and algorithms. (English) Zbl 1079.90117 J. Math. Model. Algorithms 3, No. 4, 367-402 (2004). Summary: The linear ordering problem is an NP-hard problem that arises in a variety of applications. Due to its interest in practice, it has received considerable attention and a variety of algorithmic approaches to its solution have been proposed. In this paper we give a detailed search space analysis of available benchmark instance classes that have been used in various researches. The large fitness-distance correlations observed for many of these instances suggest that adaptive restart algorithms like iterated local search or memetic algorithms, which iteratively generate new starting solutions for a local search based on previous search experience, are promising candidates for obtaining high performing algorithms. We therefore experimentally compared two such algorithms and the final experimental results suggest that, in particular, the memetic algorithm is a new state-of-the-art approach to the linear ordering problem. Cited in 1 ReviewCited in 16 Documents MSC: 90C27 Combinatorial optimization 90C59 Approximation methods and heuristics in mathematical programming 68W40 Analysis of algorithms 90B40 Search theory Keywords:linear ordering problem; search space analysis; benchmark instances; iterated local search; memetic algorithms Software:LOLIB; GraphBase PDFBibTeX XMLCite \textit{T. Schiavinotto} and \textit{T. Stützle}, J. Math. Model. Algorithms 3, No. 4, 367--402 (2004; Zbl 1079.90117) Full Text: DOI References: [3] Becker, O.: Das Helmstädtersche Reihenfolgeproblem - die Effizienz verschiedener Näherungsverfahren, in Computer Uses in the Social Science, Wien, January 1967. [29] Standard Performance Evaluation Corporation: SPEC CPU95 and CPU2000 Benchmarks, http://www.spec.org/, November 2002. This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.