Relax-and-cut algorithms for 0-1 integer programming problems

Orientador: Cid Carvalho de SouzaTese (doutorado) - Universidade Estadual de Campinas, Instituto de ComputaçãoResumo: 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.Abstract: One of the main motivations for the study of Discrete Optimization resides in the huge number of problems from our daily life that can be represented through Integer and Combinatorial Optimization models. In particular, many of these problems can be cast as 0-1 Integer Programs, which gives rise to special interest on how to solve such models. Among the several ways currently available to solve problems of this nature, the algorithms based on Lagrangian relaxation techniques appears as an alternative that has had great success in practice. Besides, noticeable achievements occurred with the advent of Polyhedral Combinatorics, intensifying the interest on cutting plane algorithms. In this context, this thesis has as its main goal to verify the potentialities of the combined usage of Polyhedral Combinatorics and Lagrangian relaxation in the resolution of two combinatorial optimization problems. More specifically, the present work is focused on the development of the so-called relax-and-cut algorithms for the set partition problem and for the vertex separator problem on graphs. Therefore, algorithms combining Lagrangian relaxation and cutting planes are proposed for the two problems under consideration. In both cases, the results obtained in the computational tests carried out are compared with the best ones available in the literature. The main results achieved in the thesis show that: (a) the combined usage of Lagrangian relaxation and cutting planes constitutes a competitive alternative to solve the set partition problem, often outperforming the best algorithms available in the literature for the problem and, (b) in the case of the vertex separator problem, besides the combination of Lagrangian techniques and cutting planes, a hybridization of the relax-and-cut and branch-and-cut algorithms lead to the resolution of instances from the literature more rapidly than the best exact algorithm known for the problem so far.DoutoradoDoutor em Ciência da Computaçã