 |
Programação Inteira: Algoritmos Exatos e Heurísticos com Aplicações em Programação de HoráriosProjeto de Pesquisa
|
Apesar dos muitos progressos que ocorreram nas últimas
décadas para a solução computacional de problemas
combinatórios difíceis, vários problemas
permanecem desafiadores tanto do ponto de vista teórico quanto
prático. A principal frente de avanço para a
resolução exata de problemas de otimização
combinatória difíceis tem sido o desenvolvimento de
técnicas de Programação Inteira (PI). Este projeto
trata de problemas com um cerne comum, que permanecem desafiadores para
o ferramental de PI disponível hoje: problemas onde devem ser
tomadas algumas entre um conjunto de decisões conflitantes. Como
primeiro e principal problema está o Problema de
Coloração de Vértices em Grafos. Considera-se
também a pesquisa e o desenvolvimento de métodos de
solução para uma conhecida aplicação deste
problema, a programação automática de quadros de
horários. Neste sentido, pretende-se trabalhar com os problemas
da Competição Internacional de Programação
de Horários. Este conjunto de instâncias apresenta
reconhecida relevância na comunidade científica pelo fato
de que mesmo a obtenção de soluções
factíveis para essas instâncias já se configura uma
tarefa computacional difícil.
Situação: Em andamento.
Orientandos: Samuel Souza Brito e Rafael Henrique Vareto
Financiamento: Conselho Nacional de Desenvolvimento Científico e Tecnológico - CNPq - Processo 480388/2010-5.