Integer programming with Gröbner bases and applications to multiobjective integer programming

Abstract

Integer programming and its multiobjective variants are important NP-hard problems with applications in graph theory, scheduling, logistics and decision making, among others. One approach to solving these classes of optimization problems that is underexplored in the literature is the algebraic approach using Gröbner basis methods, a traditional tool in the field of computational commutative algebra. The first part of this thesis improves on previous Gröbner basis algorithms for integer programming by introducing a new truncation criterion for integer programs with binary variables. This criterion is empirically shown to eliminate up to 90% of useless S-vectors in the Gröbner basis computation. These algorithms are implemented in a new state-ofthe-art open source package called IPGBs.jl. The second part of this work explores the performance of Gröbner basis methods in multiobjective integer programming. We show that these methods perform better than previously thought when implemented with efficient data structures and our new truncation criterion. Furthermore, we prove that their performance is essentially independent of the size of the Pareto front, in contrast to other criterion space algorithms, making the Gröbner basis approach particularly useful for problems with very large Pareto fronts, including those with 3 or more objectives.

Programação inteira e suas variantes multiobjetivo são importantes problemas NP-difíceis com aplicações em teoria dos grafos, agendamento, logística e tomada de decisão, dentre outras. Uma abordagem de resolução para essas classes de problemas de otimização que foi pouco explorada na literatura até o momento é a abordagem algébrica utilizando métodos de bases de Gröbner, que são ferramentas tradicionais na área da álgebra comutativa computacional. A primeira parte dessa tese apresenta melhorias em algoritmos para o cálculo de bases de Gröbner no contexto da programação inteira, introduzindo um novo critério de truncagem para programas inteiros com variáveis binárias. Mostra-se empiricamente que esse critério é capaz de eliminar até 90% dos S-vetores desnecessários no cálculo da base de Gröbner. Esses algoritmos são implementados em um novo pacote estado da arte open source chamado IPGBs.jl. A segunda parte desse trabalho explora a performance de métodos baseados em bases de Gröbner para programação inteira multiobjetivo. Mostramos que esses métodos possuem melhor desempenho do que se sabia previamente quando implementados com estruturas de dados ótimas e com nosso novo critério de truncagem. Além disso, provamos que seu desempenho é essencialmente independente do tamanho da fronteira de Pareto, em contraste com outros algoritmos que trabalham no espaço de critérios. Assim, a abordagem de bases de Gröbner se torna particularmente útil para problemas com fronteiras de Pareto muito grandes, inclusive no caso de problemas com 3 ou mais objetivos.