Defesa de Tese de Doutorado: Diego Zuquim Guimarães Garcia
Document Actions
Defesa de Tese de Doutorado: Victor Fernandes Cavalcante
Algoritmos relax-and-cut para problemas de Programação Inteira 0-1
| What | Defesa de Doutorado |
|---|---|
| When |
31/07/2008 from 13:00 to 17:00 |
| Where | sala 85 - IC2 |
| Add event to calendar |
vCal
iCal
|
Uma das principais motivações para o estudo de Otimização Discreta
reside no elevado número de problemas do nosso cotidiano
representáveis através de modelos de Otimização Inteira e
Combinatória. Em particular, muitos destes problemas podem ser
formulados com Programação Inteira 0-1, o que desperta especial
interesse em técnicas capazes de resolver tais modelos. Dentre as
inúmeras formas de solução atualmente disponíveis para problemas desta
natureza, os algoritmos baseados na técnica de relaxação Lagrangiana
surgem como uma alternativa que tem tido grande sucesso na prática.
Além disso, avanços consideráveis ocorreram na área de
Programação Inteira com o advento da Combinatória Poliédrica,
intensificando o interesse pelos algoritmos de planos de corte.
Neste contexto, esta tese tem como principal objetivo verificar as
potencialidades do uso combinado de Combinatória Poliédrica e
relaxação Lagrangiana na resolução de dois problemas de otimização
combinatória. Mais especificamente, o presente trabalho está focado
no desenvolvimento dos chamados algoritmos relax-and-cut para o
problema de particionamento de conjuntos e ao problema do separador de
vértices de um grafo.
Sendo assim, são propostos algoritmos que combinam relaxação
Lagrangiana e planos de cortes faciais para os dois problemas sob
consideração. Em ambos os casos, os resultados obtidos com os testes
computacionais realizados são comparados com os melhores resultados
disponíveis na literatura.
Os principais resultados alcançados na tese mostram que: (a) o
uso combinado de relaxação Lagrangiana e planos de corte constitui
uma alternativa bastante competitiva para solucionar o problema de
particionamento de conjuntos, frequentemente superando o desempenho
dos melhores algoritmos disponíveis na literatura para o problema e,
(b) no caso do problema do separador de vértices, além da
combinação de técnicas Lagrangianas com o uso de planos de corte, a
hibridização dos algoritmos relax-and-cut e branch-and-cut
leva à resolução de instâncias da literatura mais rapidamente que o
melhor algoritmo exato conhecido para o problema até então.
Concurso Público para Professor Doutor - MS-3
