Mathematical optimization for the visualization of complex datasets

This PhD dissertation focuses on developing new Mathematical Optimization models and solution approaches which help to gain insight into complex data structures arising in Information Visualization. The approaches developed in this thesis merge concepts from Multivariate Data Analysis and Mathematical Optimization, bridging theoretical mathematics with real life problems. The usefulness of Information Visualization lies with its power to improve interpretability and decision making from the unknown phenomena described by raw data, as fully discussed in Chapter 1. In particular, datasets involving frequency distributions and proximity relations, which even might vary over the time, are the ones studied in this thesis. Frameworks to visualize such enclosed information, which make use of Mixed Integer (Non)linear Programming and Difference of Convex tools, are formally proposed. Algorithmic approaches such as Large Neighborhood Search or Difference of Convex Algorithm enable us to develop matheuristics to handle such models. More specifically, Chapter 2 addresses the problem of visualizing a frequency distribution and an adjacency relation attached to a set of individuals. This information is represented using a rectangular map, i.e., a subdivision of a rectangle into rectangular portions so that their areas reflect the frequencies, and the adjacencies between portions represent the adjacencies between the individuals. The visualization problem is formulated as a Mixed Integer Linear Programming model, and a matheuristic that has this model at its heart is proposed. Chapter 3 generalizes the model presented in the previous chapter by developing a visualization framework which handles simultaneously the representation of a frequency distribution and a dissimilarity relation. This framework consists of a partition of a given rectangle into piecewise rectangular portions so that the areas of the regions represent the frequencies and the distances between them represent the dissimilarities. This visualization problem is formally stated as a Mixed Integer Nonlinear Programming model, which is solved by means of a matheuristic based on Large Neighborhood Search. Contrary to previous chapters in which a partition of the visualization region is sought, Chapter 4 addresses the problem of visualizing a set of individuals, which has attached a dissimilarity measure and a frequency distribution, without necessarily cov-ering the visualization region. In this visualization problem individuals are depicted as convex bodies whose areas are proportional to the given frequencies. The aim is to determine the location of the convex bodies in the visualization region. In order to solve this problem, which generalizes the standard Multidimensional Scaling, Difference of Convex tools are used. In Chapter 5, the model stated in the previous chapter is extended to the dynamic case, namely considering that frequencies and dissimilarities are observed along a set of time periods. The solution approach combines Difference of Convex techniques with Nonconvex Quadratic Binary Optimization. All the approaches presented are tested in real datasets. Finally, Chapter 6 closes this thesis with general conclusions and future lines of research.Esta tesis se centra en desarrollar nuevos modelos y algoritmos basados en la Optimización Matemática que ayuden a comprender estructuras de datos complejas frecuentes en el área de Visualización de la Información. Las metodologías propuestas fusionan conceptos de Análisis de Datos Multivariantes y de Optimización Matemática, aunando las matemáticas teóricas con problemas reales. Como se analiza en el Capítulo 1, una adecuada visualización de los datos ayuda a mejorar la interpretabilidad de los fenómenos desconocidos que describen, así como la toma de decisiones. Concretamente, esta tesis se centra en visualizar datos que involucran distribuciones de frecuencias y relaciones de proximidad, pudiendo incluso ambas variar a lo largo del tiempo. Se proponen diferentes herramientas para visualizar dicha información, basadas tanto en la Optimización (No) Lineal Entera Mixta como en la optimización de funciones Diferencia de Convexas. Además, metodologías como la Búsqueda por Entornos Grandes y el Algoritmo DCA permiten el desarrollo de mateheurísticas para resolver dichos modelos. Concretamente, el Capítulo 2 trata el problema de visualizar simultáneamente una distribución de frequencias y una relación de adyacencias en un conjunto de individuos. Esta información se representa a través de un mapa rectangular, es decir, una subdivisión de un rectángulo en porciones rectangulares, de manera que las áreas de estas porciones representen las frecuencias y las adyacencias entre las porciones representen las adyacencias entre los individuos. Este problema de visualización se formula con la ayuda de la Optimización Lineal Entera Mixta. Además, se propone una mateheurística basada en este modelo como método de resolución. En el Capítulo 3 se generaliza el modelo presentado en el capítulo anterior, construyendo una herramienta que permite visualizar simultáneamente una distribución de frecuencias y una relación de disimilaridades. Dicha visualización se realiza mediante la partición de un rectángulo en porciones rectangulares a trozos de manera que el área de las porciones refleje la distribución de frecuencias y las distancias entre las mismas las disimilaridades. Se plantea un modelo No Lineal Entero Mixto para este problema de visualización, que es resuelto a través de una mateheurística basada en la Búsqueda por Entornos Grandes. En contraposición a los capítulos anteriores, en los que se busca una partición de la región de visualización, el Capítulo 4 trata el problema de representar una distribución de frecuencias y una relación de disimilaridad sobre un conjunto de individuos, sin forzar a que haya que recubrir dicha región de visualización. En este modelo de visualización los individuos son representados como cuerpos convexos cuyas áreas son proporcionales a las frecuencias dadas. El objetivo es determinar la localización de dichos cuerpos convexos dentro de la región de visualización. Para resolver este problema, que generaliza el tradicional Escalado Multidimensional, se utilizan técnicas de optimización basadas en funciones Diferencia de Convexas. En el Capítulo 5, se extiende el modelo desarrollado en el capítulo anterior para el caso en el que los datos son dinámicos, es decir, las frecuencias y disimilaridades se observan a lo largo de varios instantes de tiempo. Se emplean técnicas de optimización de funciones Diferencias de Convexas así como Optimización Cuadrática Binaria No Convexa para la resolución del modelo. Todas las metodologías propuestas han sido testadas en datos reales. Finalmente, el Capítulo 6 contiene las conclusiones a esta tesis, así como futuras líneas de investigación.Premio Extraordinario de Doctorado U