Mapas de símbolos proporcionais

Nesta dissertacao, realizamos um estudo extensivo de uma classe de problemas envolvendo mapas de simbolos proporcionais, atraves de programacao linear inteira. Mapas de simbolos proporcionais sao uma ferramenta cartografica para a representacao de eventos associados `a intensidade e localizacao geografica. Exemplos classicos desses tipos de mapas sao ocorrencias de terremotos e populacoes de cidades. Devido `a proximidade e ao tamanho dos simbolos, podem haver sobreposicoes entre eles. Na ocorrencia dessas sobreposicoes, a decisao sobre quais simbolos ficarao por cima de outros, pode afetar a visibilidade dos simbolos em um desenho. Os problemas envolvendo mapas de simbolos proporcionais dos quais tratamos sao restritos ao uso de circulos opacos como simbolos e consistem em decidir a ordem em que estes serao dispostos em vista das sobreposicoes, de forma a maximizar metricas associadas a qualidade visual desses mapas. Tratam-se, portanto, de problemas de otimizacao combinatoria. Em nosso trabalho, apresentamos modelos de programacao linear inteira para resolucao de dois desses problemas, um deles foi provado pertencer a classe NP-dificil e o outro tem complexidade ainda nao conhecida. Obtivemos resultados teoricos de combinatoria poliedrica acerca dos modelos, o que resultou em diversas desigualdades definidoras de facetas que foram incorporadas aos modelos. Desenvolvemos ainda tecnicas de pre-processamento que decompuseram as instâncias de entrada em um grande numero de componentes de menor tamanho. Essas tecnicas permitiram resolver de maneira otima, pela primeira vez, diversas instâncias criadas a partir de dados reais. Ademais, descrevemos um trabalho que aborda um desses problemas atraves de uma heuristica GRASP, ao qual tambem contribuimos Abstract