Defesa de doutorado do discente Thiago Alcântara, dia 04/07/2025 às 13:00.

Defesa de doutorado do discente Thiago Alcântara, dia 04/07/2025 às 13:00.

Título: Cover by Disjoint Clique Cuts and Machine Learning to Assist Mixed-Integer Linear Programming Solvers

Abstract: Cutting planes and primal heuristics are two of the most important components of modern mixed-integer linear programming (MILP) solvers. To improve both the strength of MILP formulations and the process of identifying feasible integer solutions, this thesis presents two key contributions. First, we propose a family of strong cutting planes for the knapsack problem with conflicting items and prove that a subfamily of these cuts can be facet defining. The computational experiments demonstrate that the proposed cuts effectively reduce integrality gaps, providing dual bounds up to 78% tighter than formulations strengthened with traditional combinatorial cuts. We also show that it is possible to adapt a recently proposed lifting procedure to further strengthen the proposed cuts. Second, we propose a machine learning-based recommendation system that identifies the most suitable diving heuristic (a type of primal heuristic) and whether it should be combined with cutting planes and/or feasibility pump. These recommendations are based on 207 features extracted from the MILP problem. The computational results show that the recommendation system leads to the discovery of feasible solutions in 87% of the possible cases. This corresponds to 10% more feasible integer solutions than the best diving heuristic combined with feasibility pump and cutting planes, while requiring only 52% of the total runtime.

Banca examinadora: Prof. Marcone Jamilson Freitas Souza (Orientador, UFOP); Tulio Ângelo Machado Toffolo (Coorientador, Amazon); Prof. Anand Subramanian (UFPB); Profa. Elisangela Martins de Sá (CEFET-MG); Haroldo Gambini Santos (Amazon); Prof. Puca Huachi Vaz Penna (UFOP).

Link da videochamada: https://meet.google.com/cir-iqqa-aij