×

The linear ordering problem: instances, search space analysis and algorithms. (English) Zbl 1079.90117

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.

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
68W40 Analysis of algorithms
90B40 Search theory

Software:

LOLIB; GraphBase
PDFBibTeX XMLCite
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.