# Linear Ordering Problem: Time for a Change

arXiv: https://arxiv.org/abs/2605.31051 · HTML: https://mlsanity.com/paper/2605.31051/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 51 references that are in the map.
- First posted on arXiv 29 May 2026.

## Builds on (most cited first, 5 of 5)

- [Analysis of Evolutionary Diversity Optimisation for Permutation Problems](https://mlsanity.com/paper/2102.11469/) (2021)
- [On the Linear Ordering Problem and the Rankability of Data](https://mlsanity.com/paper/2104.05816/) (2021)
- [Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem](https://mlsanity.com/paper/2010.10913/) (2020)
- [A Diversity-Aware Memetic Algorithm for the Linear Ordering Problem: Improving Best-Known Solutions for Standard Benchmarks](https://mlsanity.com/paper/2106.02696/) (2021)
- [Theoretical and Empirical Analysis of Lehmer Codes to Search Permutation Spaces with Evolutionary Algorithms](https://mlsanity.com/paper/2511.19089/) (2025)

## Abstract (arXiv)

The Linear Ordering Problem (LOP) is a fundamental combinatorial optimization problem with important applications in areas such as economics, social choice, and machine learning. Its most prominent use is the triangulation of economic input-output tables, which helps identify critical industries in an economy. Most existing algorithms have been evaluated on benchmarks derived from outdated macroeconomic data, which no longer reflect the structure of contemporary economies. Furthermore, LOP instances often exhibit many distinct global optima that can differ substantially from one another, creating challenges for applications that rely on a single solution. To address these limitations, we introduce a novel benchmark suite derived from up-to-date real-world economic data and an algorithmic scheme that leverages state-of-the-art LOP metaheuristics to generate diverse sets of high-quality solutions, together with metrics for assessing both quality and diversity. Experiments were conducted to report results on the proposed benchmark suite under both the traditional single-solution setting and the newly introduced multi-solution scenario