Soluções exatas para o Problema Cromático da Galeria de Arte

Nesta dissertacao, apresentamos a primeira abordagem algoritmica e os primeiros resultados experimentais da literatura para tratamento do Problema Cromatico Discreto da Galeria de Arte (DCAGP). Trata-se de um problema de natureza geometrica que consiste de uma variante do classico Problema da Galeria de Arte. Neste, deseja-se encontrar um conjunto de guardas com cardinalidade minima que consiga vigiar toda uma dada galeria. Ja no DCAGP temos por objetivo obter um conjunto de observadores que cubra a galeria e que admita uma coloracao valida com o menor numero de cores. Uma coloracao e valida se dois observadores que veem um mesmo ponto recebem cores distintas. Abordamos a resolucao deste problema atraves de duas abordagens: uma exata e uma heuristica. Inicialmente, apresentamos uma heuristica primal que fornece limitantes superiores de boa qualidade e, em seguida, um modelo de programacao linear inteira para resolucao exata do DCAGP. Este metodo foi capaz de resolver todas as instâncias de um extenso conjunto de galerias, representadas por poligonos simples aleatoriamente gerados, de ate 2500 vertices, em menos de um minuto. Ja num outro conjunto de instâncias onde a representacao inclui poligonos com buracos e poligonos fractais de von Koch com ate 800 vertices, o metodo encontrou solucoes comprovadamente otimas para 80% das instâncias em menos de 30 minutos. No contexto dessas solucoes, discutimos o uso de lazy-constraints e de tecnicas de fortalecimento do modelo, assim como uma breve analise da dificuldade das instâncias. Reportamos ainda resultados da utilizacao de relaxacao Lagrangiana, para obtencao de bons limitantes, principalmente superiores, e tambem resultados obtidos por meio de uma variacao da tecnica relax-and-fix. Finalmente, discutimos um processo de branch-and-price para resolucao exata do DCAGP. Abstract