Integer Linear Programming reformulations for the linear ordering problem

Nicolas Dupin (1, 2)

1 LISN - Laboratoire Interdisciplinaire des Sciences du Numérique
2 ROCS - Réseaux & Optimisation Combinatoire et Stochastique - LISN

This article studies the linear ordering problem, with applications in social choice theory and databases for biological datasets. Integer Linear Programming (ILP) formulations are available for the linear ordering problem and some extensions. ILP reformulations are proposed, showing relations with the Asymmetric Travel Salesman Problem. If a strictly tighter ILP formulation is found, numerical results justify the quality of the reference formulation for the problem in the Branch& Bound convergence, and the quality of the continuous relaxation to design rounding heuristics. This work offers perspectives to design matheuristics for the linear ordering problem and extensions.

Keywords: Optimization; Integer Linear Programming; Linear ordering problem; Median of permutations; Consensus ranking; Polyhedral analysis

Domains: Optimization and Control [math.OC]; Computer Science [cs]; Operations Research [math.OC]

Nicolas Dupin. Integer Linear Programming reformulations for the linear ordering problem. 2022. ⟨hal-03607145⟩