O Programa de Pós-Graduação em Modelagem e Métodos Quantitativos (PPGMMQ) convida a comunidade acadêmica para o seminário a ser apresentado por Phablo Moura, ex-aluno do grupo e atualmente pesquisador na Katholieke Universiteit Leuven, Bélgica.
Título:
Covering and packing mixed-integer linear programs: Approximation and convex hull
Local: Sala de Seminários do Bloco 952
Data: 17/04/2026
Hora: 13h
📝 Resumo:
This talk presents an algorithmic study of a class of covering mixed-integer linear programming problems which encompasses classic cover problems, including multidimensional knapsack, facility location and supplier selection problems. We first show some properties of optimal solutions, which are then used to decompose the problem into instances of the multidimensional knapsack cover problem with a single continuous variable per dimension. The proposed decomposition is used to design a polynomial-time approximation scheme for the problem with a fixed number of constraints. To the best of our knowledge, this is the first approximation scheme for such a general class of covering mixed-integer linear programs. Moreover, we design a fully polynomial-time approximation scheme and an approximate linear programming formulation for the case with a single constraint. These results improve upon the previously best-known 2-approximation algorithm for the knapsack cover problem with a single continuous variable. Finally, we show a perfect compact formulation for the case where all variables have the same lower and upper bounds. Analogous results are derived for the packing and more general variants of the problem.
⚠️ Importante: A participação neste seminário contará como carga horária para a disciplina de Seminários, mediante registro de presença.
O evento é aberto à comunidade acadêmica.
