Algoritmos relax-and-cut para problemas de programação inteira 0-1 / Relax-and-cut algorithms for 0-1 integer programming problems
AUTOR(ES)
Victor Fernandes Cavalcante
DATA DE PUBLICAÇÃO
2008
RESUMO
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 esta 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, freqüentemente 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-andcut leva á resolução de instâncias da literatura mais rapidamente que o melhor algoritmo exato conhecido para o problema até então
ASSUNTO(S)
integer programming algorithms otimização combinatoria combinatorial optimization programação inteira algoritmos
ACESSO AO ARTIGO
http://libdigi.unicamp.br/document/?code=000434044Documentos Relacionados
- ALGORITHM RELAX-AND-CUT FOR THE 0-1 QUADRATIC KNAPSACK PROBLEM
- Um estudo computacional da busca tabu paramétrica para programação inteira mista 0-1
- Algorithms for nonlinear programming problems with integer and continuous variables.
- Uso de cortes canonicos no metodo de ramificação local para problemas inteiros 0-1 mistos
- INTEGER PROGRAMMING PROBLEMS ON TELECOMMUNICATIONS OPTICAL NETWORKS