O Poliedro das Orientações Acíclicas de Um Grafo Sob Restrições e Suas Aplicações

Alguns problemas de otimização combinatória podem ser resolvidos procurando-se por uma orientação ótima de um grafo, segundo alguma medida de otimalidade. No Problema de Coloração, cada orientação $\\omega$ de um grafo $G$ estabelece um limite superior para o número cromático $\\chi(G)$ igual ao tamanho do maior caminho elementar entre qualquer par de vértices em $G$, orientado segundo $\\omega$. Mais do que isso, o valor exato de $\\chi(G)$ é alcançado procurando-se pelo menor destes limites sobre o conjunto de todas as orientações acíclicas de $G$. O Problema de Alocação de Freqüências, fortemente relacionado ao Problema de Coloração, é um outro exemplo: suas soluções ótimas estão relacionadas com o conjunto das orientações acíclicas com restrições de caminho de um grafo. Nesta tese, introduzimos modelos de programação linear inteira para as orientações acíclicas com restrições de caminho e discutimos seu uso na solução dos Problemas de Coloração e de Alocação de Freqüências. Apresentamos um estudo parcial dos poliedros associados, verificando quais das desigualdades do modelo definem facetas do poliedro e introduzindo novas classes de desigualdades válidas e definidoras de facetas. Finalmente, descrevemos a implementação de um algoritmo "branch-and-cut" que utiliza os modelos apresentados, analisando suas vantagens e limitações quando aplicados na resolução do Problema de Coloração.