Determinación experimental de la influencia de la reformulación del problema RAP en su eficiencia computacional

Randy Reyna Hernández, Alejando Rosete Suárez

Resumen


El problema de agregación de rankings (RAP, por sus siglas en inglés) busca encontrar un ranking que resuma un conjunto de ellos. Actualmente, el razonamiento sobre la base de ordenamientos o rankings ha ganado gran atención debido al gran número de aplicaciones para solucionar problemas de toma de decisiones y más recientemente, en informática, estadística, algebra lineal y optimización, la biología computacional entre muchas otras. Dentro del contexto de RAP se encuentra el Problema del Ranking de Kemeny (KRP), donde todos los rankings de entrada son una permutación. El KRP es NP-duro, sin embargo, existe una formulación donde, a través del método de Programación Lineal Entera (PLE) se le puede dar solución al problema. Como la eficiencia del método de PLE está dada por la cantidad de variables y restricciones, se obtuvo una reformulación del problema que permite reducir ambas dimensiones. En el presente trabajo se demuestra como la reformulación del RAP permite resolver con el mismo software instancias mayores y de resolver las mismas en menos tiempo.


Palabras clave


Agregación de Rankings, Programación Lineal Entera, Plugins de KNIME

Texto completo:

PDF

Enlaces refback

  • No hay ningún enlace refback.




_________________________________________________________________________________________________________

La Universidad de las Ciencias Informáticas (UCI), a través del sello editorial Ediciones Futuro, publica los contenidos de la Revista Cubana de Ciencias Informáticas (RCCI) bajo licencia Creative Commons de tipo Atribución 4.0 Internacional (CC BY 4.0). Esta licencia permite a otros distribuir, mezclar, ajustar y construir a partir de su obra, incluso con fines comerciales, siempre que le sea reconocida la autoría de la creación original.
_________________________________________________________________________________________________________

 INDEXACIÓN