A review on discrete diversity and dispersion maximization from an OR perspective

Abstract

El problema de la maximización de la diversidad o la dispersión consiste en seleccionar un subconjunto de elementos de un conjunto dado de tal forma que se maximice la distancia entre los elementos seleccionados. La definición de distancia entre elementos se adapta a aplicaciones específicas, y la forma de calcular la diversidad global de los elementos seleccionados da lugar a distintos modelos matemáticos. La maximización de la diversidad mediante modelos de optimización combinatoria ha ganado importancia en la Investigación Operativa (IO) durante las dos últimas décadas, y constituye hoy en día un área importante. En este trabajo se revisan los hitos en el desarrollo de esta área, comenzando a finales de los ochenta cuando se propusieron los primeros modelos, y se identifican tres periodos de tiempo. El análisis crítico desde una perspectiva OR de los desarrollos anteriores, nos permite establecer los modelos más apropiados, su conexión con los problemas prácticos en términos de dispersión y representatividad, y los problemas abiertos que todavía suponen un reto. También revisamos y ampliamos la biblioteca de instancias de referencia que se ha utilizado ampliamente en las comparaciones heurísticas. Por último, realizamos una revisión empírica y una comparación de los mejores procedimientos y de los propuestos más recientemente, para identificar claramente los métodos más avanzados para los principales modelos de diversidad.