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

DOI10.1007/s10852-005-2583-1zbMath1079.90117OpenAlexW2003755947MaRDI QIDQ1774626

Thomas Stützle, Tommaso Schiavinotto

Publication date: 17 May 2005

Published in: JMMA. Journal of Mathematical Modelling and Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10852-005-2583-1

zbMATH Keywords

iterated local searchbenchmark instancesmemetic algorithmslinear ordering problemsearch space analysis

Mathematics Subject Classification ID

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

Related Items

A heuristic framework on a common generalization of the vehicle routing problem and the linear ordering problem ⋮ The linear ordering problem revisited ⋮ A survey on the linear ordering problem for weighted or unweighted tournaments ⋮ Generating new test instances by evolving in instance space ⋮ Fairness and the set of optimal rankings for the linear ordering problem ⋮ A review of distances for the Mallows and generalized Mallows estimation of distribution algorithms ⋮ A linear ordering problem with weighted rank ⋮ A benchmark library and a comparison of heuristic methods for the linear ordering problem ⋮ Randomized Algorithms for Lexicographic Inference ⋮ An Experimental Comparison of Algebraic Crossover Operators for Permutation Problems ⋮ Heuristic implementation of dynamic programming for matrix permutation problems in combinatorial data analysis ⋮ Efficient local search algorithms for the linear ordering problem ⋮ Metaheuristics for Score-and-Search Bayesian Network Structure Learning ⋮ An updated survey on the linear ordering problem for weighted or unweighted tournaments ⋮ Comparing Two Samples Through Stochastic Dominance: A Graphical Approach ⋮ Block-insertion-based algorithms for the linear ordering problem

Uses Software

• GraphBase
• LOLIB

Cites Work

• Optimization by Simulated Annealing
• Correlated and uncorrelated fitness landscapes and how to tell the difference
• Autocorrelation coefficient for the graph bipartitioning problem
• A branch and bound algorithm for the acyclic subgraph problem
• Intensification and diversification with elite tabu search solutions for the linear ordering problem
• Landscapes and their correlation functions
• An experimental evaluation of a scatter search for the linear ordering problem
• On the classification of NP-complete problems in terms of their correlation coefficient
• A Cutting Plane Algorithm for the Linear Ordering Problem
• The landscape of the traveling salesman problem