Algoritmos eficientes para Problemas de Otimização Combinatória

Descrição

Este projeto tem como objetivo desenvolver algoritmos exatos ou heurísticos para a solução de problemas de otimização de natureza combinatória e elevada complexidade computacional, utilizando ferramentas das áreas de otimização combinatória e teoria dos grafos. Muitos problemas reais de natureza combinatória podem ser modelados por modelos matemáticos discretos, como grafos, por exemplo. A solução destes problemas frequentemente exige uma abordagem algorítmica, juntamente com a implementação destes algoritmos em algum sistema computacional. É importante ressaltar a necessidade de obter algoritmos eficientes, pois tipicamente tanto o volume de dados como a frequência de acessos ao sistema são grandes. Para ilustrar a diversidade de áreas, os problemas ocorrem no projeto de redes de telecomunicações, planejamento de horários, projeto de redes de escoamento de produtos, projeto de circuitos VLSI, corte de materiais, empacotamento em containers, localização de centros distribuidores, escalonamento de tarefas, roteamento de veículos, sequenciamento de DNA, etc. Alguns problemas de otimização combinatória podem ser bem resolvidos, i.e., possuem complexidade polinomial, mas para muitos outros não são esperados algoritmos exatos e rápidos para problemas de grande porte (pertencem à classe NP-difícil). Como os problemas em questão possuem complexidade intrinsecamente alta, uma possibilidade é recorrer a um algoritmo heurístico — que produz uma solução próxima do ótimo em um curto período de tempo — em vez de um algoritmo exato (complexidade exponencial). Isto se deve à relevância de tais problemas além da necessidade da obtenção de boas soluções, mesmo que elas não sejam ótimas. Neste projeto, cada discente participante possui um plano de trabalho voltado à busca de uma solução algorítmica para um problema NP-difícil distinto. Dentre as várias soluções que o discente poderá abordar destacam-se: algoritmos exatos; algoritmos heurísticos e meta-heurísticas, além de abordagens híbridas com métodos exatos. Dentro do contexto descrito acima, o foco deste projeto é atacar problemas de otimização de natureza combinatória, desenvolvendo algoritmos competitivos para a solução destes problemas.