Resumen de Nuevos problemas de agregación de rankings: modelos y algoritmos
Eva M. García Nové
Los problemas relacionados con los rankings y la agregación de los mismos han sido muy estudiados en la literatura y siguen siéndolo en la actualidad, ya que en muy diversas situaciones de la vida real continuamente se necesita saber qué posición ocupa un determinado dato. Problemas como el "Linear Ordering Problem" o el "Rank Aggregation Problem" siguen estudiándose en todas sus variantes.
Esta memoria se centra en el estudio de nuevos problemas de agregación de rankings no contemplados en la literatura. Podemos separarlos en tres grupos diferenciados, cada uno con dos nuevos problemas. El primer grupo lo constituye una variante del problema de ordenamiento lineal en el caso de disponer de rankings cíclicos, y del conocido problema del viajante de comercio en caso de existir la posibilidad de permutación de nodos. El segundo grupo contempla la posibilidad de que el conjunto de elementos iniciales esté separado en clústeres y solo tengamos que obtener un ranking parcial, eligiendo un elemento de cada clúster. Por último, se presentan dos problemas que contemplan la posibilidad de disponer de elementos separados en clústeres y se quiere obtener un ranking parcial cíclico que cumpla determinadas premisas.
Para los nuevos problemas que se han introducido, se proponen técnicas de resolución de distintos tipos: exactas y heurísticas. Las técnicas exactas, basadas en modelos de programación lineal, no son aplicables en instancias de determinado tamaño, debido a que son problemas de optimización combinatoria NP-duros. Por ello también se han diseñado técnicas metaheurísticas que, haciendo uso de operados que incorporan conocimiento específico del problema, consiguen soluciones de calidad en un tiempo de computación aceptable.
