Árvores Ótimas em Grafos: Modelos, Algoritmos e Aplicações

Nesta Tese, apresentamos modelos, formulações e algoritmos para problemas que, a menos de algumas restrições adicionais, podem ser entendidos como problemas de determinação de árvores ótimas em grafos. Três problemas foram estudados: o Problema da Árvore Geradora de Custo Mínimo com Restrição de Grau nos Vértices (PARG), o Problema da Árvore de Steiner com Recolha de Prêmios (PASRP) e, finalmente, o Problema de Planejamento da Extração de Madeira (PPEM). Apresentamos um estudo poliedral do PARG que nos permitiu introduzir algoritmos exatos e heurísticas pelo menos tão bons quanto os melhores da literatura. Após procedermos a uma reformulação do PASRP, introduzimos uma heurística Lagrangeana competitiva, com vários ingredientes novos. Introduzimos uma nova modelagem do PPEM que poderá permitir que instâncias reais, de maiores dimensões, sejam resolvidas na otimalidade. Uma contribuição adicional desta Tese foi um procedimento que propusemos para tentar caracterizar um ponto extremo de uma árvore geradora. Tal procedimento pode ser estendido a problemas que admitam relaxações definidas sobre matróides e permite transportar limites duais Lagrangeanos para um algoritmo de Planos de Corte sem a necessidade de resolver qualquer problema de separação.