Publicado em: 14/07/2025

Defesa – Tese de Gabriel Mattos Langeloh

Aluno(a): Gabriel Mattos Langeloh
Orientador(a): Marcus Rolf Peter Ritt

Título: Integer Programming with Gröbner Bases and Applications to Multiobjective Integer Programming
Linha de Pesquisa: Algoritmos e Otimização

Data: 14/07/2025
Hora: 12:00
Local: Esta banca ocorrerá de forma híbrida (virtual e presencial), na sala Completamente virtual do Instituto de Informática/UFRGS e pelo link https://mconf.ufrgs.br/webconf/00154932.

Banca Examinadora:
-André Grahl Pereira (Universidade Federal do Rio Grande do Sul)
-Serkan Hosten (San Francisco State University)
-José María Ucha Enríquez (Universidad de Sevilla)

Presidente da Banca: Marcus Rolf Peter Ritt

Resumo: 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-of-the-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.

Palavras-Chave: Integer Programming; Multiobjective Integer Programming; Gröbner Bases