discrete optimization models in data visualization

Abstract

Data visualization techniques have become important tools for analyzing large multidimensional data sets and providing insights with respect to scientific, economic, and engineering applications. Typically, these visualization applications are modeled and solved using nonlinear optimization techniques. In this dissertation, we propose a discretization of the data visualization problem that allows us to formulate it as a quadratic assignment problem. This formulation is computationally difficult to solve optimally using an exact approach. Consequently, we investigate the use of local search techniques, mathematical programming, and genetic algorithms for the data visualization problem. The space in which the data points are to be embedded can be discretized using an n x n lattice. Conducting a search on this n x n lattice is computationally ineffective. Consequently, we propose a divide-and-conquer approach that refines the lattice at each step. We show that this approach is much faster than conducting a search of the entire n x n lattice and, in general, it generates higher quality solutions. We envision two uses of our divide-and-conquer heuristics: (1) as stand-alone approaches for data visualization and (2) to provide good approximate starting solutions for a nonlinear algorithm.