O Poliedro das Orientações Acíclicas de Um Grafo Sob Restrições e Suas Aplicações
Autores
4499 |
44,163,693
|
|
4500 |
44,163,693
|
|
4501 |
44,163,693
|
Informações:
Publicações do PESC
Título
O Poliedro das Orientações Acíclicas de Um Grafo Sob Restrições e Suas Aplicações
Linha de pesquisa
Otimização
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
10/6/2005
Resumo
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.
Abstract
Arquivo