Orientador: Pedro Jussieu de Rezende, Cid Carvalho de Souza

Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação

Resumo: Nesta dissertação, realizamos um estudo extensivo de uma classe de problemas envolvendo mapas de símbolos proporcionais, através de programação linear inteira. Mapas de símbolos proporcionais são uma ferramenta cartográfica para a representação de eventos associados 'a intensidade e...

Resumo: Nesta dissertação, realizamos um estudo extensivo de uma classe de problemas envolvendo mapas de símbolos proporcionais, através de programação linear inteira. Mapas de símbolos proporcionais são uma ferramenta cartográfica para a representação de eventos associados 'a intensidade e localização geográfica. Exemplos clássicos desses tipos de mapas são ocorrências de terremotos e populações de cidades. Devido 'a proximidade e ao tamanho dos símbolos, podem haver sobreposições entre eles. Na ocorrência dessas sobreposições, a decisão sobre quais símbolos ficarão por cima de outros, pode afetar a visibilidade dos símbolos em um desenho. Os problemas envolvendo mapas de símbolos proporcionais dos quais tratamos são restritos ao uso de círculos opacos como símbolos e consistem em decidir a ordem em que estes serão dispostos em vista das sobreposições, de forma a maximizar métricas associadas à qualidade visual desses mapas. Tratam-se, portanto, de problemas de otimização combinatória. Em nosso trabalho, apresentamos modelos de programação linear inteira para resolução de dois desses problemas, um deles foi provado pertencer à classe NP-difícil e o outro tem complexidade ainda não conhecida. Obtivemos resultados teóricos de combinatória poliédrica acerca dos modelos, o que resultou em diversas desigualdades definidoras de facetas que foram incorporadas aos modelos. Desenvolvemos ainda técnicas de pré-processamento que decompuseram as instâncias de entrada em um grande número de componentes de menor tamanho. Essas técnicas permitiram resolver de maneira ótima, pela primeira vez, diversas instâncias criadas a partir de dados reais. Ademais, descrevemos um trabalho que aborda um desses problemas através de uma heurística GRASP, ao qual também contribuímos

Abstract: In this dissertation, we present an extensive study of a class of problems involving proportional symbol maps, through integer linear programming. Proportional symbol maps are a cartographic tool to represent events associated to specified values and geographical coordinates. Classic...

Abstract: In this dissertation, we present an extensive study of a class of problems involving proportional symbol maps, through integer linear programming. Proportional symbol maps are a cartographic tool to represent events associated to specified values and geographical coordinates. Classic examples of these maps include representation of earthquakes and city populations. Due to the size and proximity of the symbols, there may be overlap among them. In such case, deciding which symbols will be placed above others may result in maps with different visibility information. The problems dealing with proportional symbol maps we address restrict symbols to be opaque disks and consist of deciding the order of their placement in view of overlaps, so as to maximize metrics related to the visual quality of such maps. Therefore, these amount essentially to combinatorial optimization problems. In our work, we designed integer linear programming models to solve two of these problems, one proven to be NP-hard and the other of complexity yet unknown. We obtained theoretical results concerning these models, through polyhedral combinatorics, which allowed us to include several facet defining inequalities into these models. We also developed preprocessing techniques that successfully broke down the input instances into a large number of smaller components. These techniques lead, for the first time, to optimal solutions of several test instances created from real-world data. Furthermore, we describe work on a heuristic approach to one of these problems using GRASP, to which we also contributed