Abstract:The linear ordering problem (LOP) is a classical NP-hard combinatorial optimization problem. In this paper, we study constructive heuristics for the LOP. We propose a unified recursive framework in which the index set is heuristically partitioned into smaller subsets, sufficiently small subproblems are solved exactly, and the resulting permutations are concatenated. Within this framework, we investigate three different recursive partitioning principles: a rule based on strongly connected components (the level graph method), a cut-based rule (the minimum cut method), and a score-based rule (the recursive Borda method). We first show that the recursive Borda method satisfies the Condorcet criterion, whereas the Borda rule does not. The level graph method and the minimum cut method satisfy a stronger Condorcet-type property, which the recursive Borda method does not satisfy. Computational experiments on xLOLIB instances show that the recursive Borda method provides the best average solution quality among the tested constructive heuristics. They also show that, after applying insertion-based local search, the differences in final solution quality among these heuristics become much smaller.
From: Kazutoshi Ando [view email]
[v1]
Tue, 23 Jun 2026 13:25:42 UTC (42 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。