Investigating the Intersection of Ranking-Based Approaches in Combinatorial Optimization

M. Beristain Cortes, L. Hernando Rodriguez, J. A. Lozano Alonso

In combinatorial optimization, many algorithms treat the problem of finding optimal solutions as one of ranking, where only the relative ordering of solutions is considered, not their exact values. This implies that algorithms can exhibit similar behavior when solving different combinatorial optimization problems if the rankings of solutions are the same. In this paper, we explore the intersection of two well-known combinatorial optimization problems, the Linear Ordering Problem (LOP) and the Traveling Salesperson Problem (TSP), from the perspective of solution rankings.
We investigate the conditions under which rankings belong to both the LOP and the TSP and provide bounds on the number of such intersecting rankings. Furthermore, we propose a conjecture concerning the complexity of the set of rankings common to these two problems. Our work provides insight into how ranking-based algorithms might behave when applied to problems sharing similar solution orderings.

Keywords: Permutation-based combinatorial optimisation problems, rankings, linear ordering problem, asymmetric traveling salesperson problem

Heuristics and Metaheuristics II
June 10, 2025  5:10 PM
MR 1

A. Casado, S. Pérez-Peló, J. Sánchez-Oro, A. Duarte, M. Laguna

S. Gil Borrás, E. G. Pardo

N. H. Rodriguez Uribe, A. Herrán González, J. M. Colmenar