Reformulación eficiente del problema de programación lineal de agregación de rankings/Efficient reformulation of the linear programming rank aggregation problem

Alejandro Rosete-Suárez

Resumen


Los rankings son muy utilizados para expresar distintos tipos de preferencias, en ramas tan diversas como la música, el deporte, la política, etc. El problema de agregación de rankings consiste en encontrar la permutación que mejor resume a un conjunto de rankings de entrada, minimizando la distancia de Kendall. Existe una formulación de programación lineal entera para este problema que permite su resolución de forma exacta si se cuenta con los recursos computacionales necesarios. En este trabajo se presenta una nueva formulación de programación lineal entera del problema de agregación de rankings que permite reducir las variables a la mitad y la cantidad de restricciones a un tercio aproximadamente. Esto permite resolver los mismos problemas con mucha mayor eficiencia computacional.

Abstract

Rankings are very commonly used to express preferences in music, sports, politics and other diverse fields. The Rank Aggregation Problem consists on finding the permutation that best represents a set of input rankings, by minimizing the Kendall distance. There is an Integer Linear Programming formulation for this problem that allows solving it in an exact way, if computational resources are available. In this paper we introduce a new Integer Linear Programming formulation of the Rank Aggregation Problem that allows reducing the number of variables by half and the amount of constraints approximately to a third part. This reduction allows solving the same problems with an improved computational efficiency.   


Palabras clave


agregación de rankings, programación lineal entera, distancia de Kendall, rank aggregation, integer linear programming, Kendall distance

Texto completo:

PDF


 

 

 

 

 

 

 

 

Dirección editorial:

Facultad de Ingeniería Industrial, Instituto Superior Politécnico José Antonio Echeverría, Cujae,

Calle 114 No. 11901. e/ Ciclovía y Rotonda. Marianao 15.

La Habana, Cuba. CP 19390. Telf: (537) 266 3521

E-mail: revistaii@ind.cujae.edu.cu

URL: http://rii.cujae.edu.cu