The linear ordering problem: instances, search space analysis and algorithms

The linear ordering problem: instances, search space analysis and algorithms

0.00 Avg rating0 Votes
Article ID: iaor20051475
Country: Netherlands
Volume: 3
Issue: 4
Start Page Number: 367
End Page Number: 402
Publication Date: Dec 2004
Journal: Journal of Mathematical Modelling and Algorithms
Authors: ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.