Linear ordering problem with heterogeneous preference groups

J. Á. Aledo Sánchez, C. Domínguez Sánchez, J. D. Jaime Alcántara, M. Landete Ruiz

The classical linear ordering problem assumes homogeneous preferences, failing when data stems from multiple latent groups with distinct patterns. To address this, we introduce an extension that partitions the population into latent groups, each characterized by its own linear order, size, and preference structure. We develop mixed-integer programming formulations, including a compact geometric reformulation, to model the observed preference matrix as the aggregate of these groups. Because exact solutions are computationally demanding for larger instances, we propose a multi-start alternating-direction heuristic that iteratively updates group rankings and weights. Computational experiments on synthetic data demonstrate that while the exact approach successfully recovers the underlying groups, the heuristic delivers high-quality solutions significantly faster, occasionally outperforming the exact method on difficult instances within time limits.

Palabras clave: Combinatorial optimization, Linear Ordering Problem, Rank aggregation, Heterogeneous populations, Mixed-integer programming

GT GELOCA V: Location and routing with preferences
5 de septiembre de 2026  16:00
Aula B

J. A. Aledo, C. Domínguez Sánchez, J. D. Jaime-Alcántara, M. Landete

H. I. Calvete, C. Galé, A. Hernández, J. A. Iranzo

P. Segura Martínez, C. Domínguez Sánchez