Estudo de problemas de otimização combinatória relacionados a visualização de dados

Resumo

O processo de tomada de decisão, no contexto de pesquisa operacional, envolve, fundamentalmente, a análise de dados relevantes à aplicação considerada. Em diversas situações, a visualização dos dados em mapas e diagramas torna esse processo muito mais eficaz e pode ser de grande valia para gerentes e administradores. A necessidade de produzir tais visualizações automaticamente dá origem a diversos problemas computacionalmente difíceis de otimização combinatória. Neste documento, discutimos dois problemas relacionados ao tema. Em um deles, eventos são representados por símbolos opacos, os quais podem se sobrepor. Assim, deve-se determinar a ordem na qual eles devem ser desenhados para evitar que alguns deles sejam encobertos. O outro problema envolve a disposição de rótulos em mapas interativos, nos quais é permitido alterar a escala ou efetuar rotações. Porém, deseja-se que a orientação e o tamanho dos rótulos na visualização permaneçam constantes. Conforme o usuário altera a escala ou rotaciona o mapa, sobreposições entre rótulos podem surgir. Dessa forma, deve-se determinar em quais escalas ou ângulos de rotação cada rótulo pode ser exibido, de forma a eliminar sobreposições. O objetivo deste projeto é desenvolver métodos para a obtenção de soluções ótimas ou quase ótimas para esses problemas e, possivelmente, para outros semelhantes. Algoritmos exatos serão desenvolvidos através de técnicas de programação linear inteira, enquanto que heurísticas serão utilizadas para encontrar soluções de alta qualidade rapidamente. A eficiência dos algoritmos implementados será avaliada através de experimentos com instâncias baseadas em dados reais. (AU)