Defesa de doutorado de Samuel Brito, dia 28/02/20 as 09:00 horas, sala de seminários do DECOM

Defesa de doutorado de Samuel Brito, dia 28/02/20 as 09:00 horas, sala de seminários do DECOM

Título: Conflict Graphs in Mixed-Integer Linear Programming: Preprocessing, Heuristics and Cutting Planes

Resumo: This thesis addresses the development of conflict graph-based routines for Mixed-Integer Linear Programming, including: (i) a conflict graph infrastructure with an improved version of a state-of-the-art conflict detection algorithm to quickly build conflict graphs: this version detects additional conflicts and has the same worst-case complexity of the original algorithm; (ii) a preprocessing routine based on a clique merging scheme that can both reduce the number of constraints and also produce stronger formulations; (iii) a clique cut separator capable of obtaining dual bounds at the root node that are 19.64% stronger than the ones provided by the equivalent cut generator of a state-of-the-art commercial solver, 3.62 times better than those attained by the clique cut separator of the GLPK solver and 4.22 times stronger than the dual bounds obtained by the clique separation routine of the COIN-OR Cut Generation Library; (iv) an odd-cycle cut separator with a new lifting module to produce valid odd-wheel inequalities; (v) two diving heuristics capable of generating integer feasible solutions in restricted execution times. Additionally, we generated a customized version of the COIN-OR Branch-and-Cut (CBC) solver, including in it our conflict graph infrastructure, preprocessing routine and cut separators. This version of CBC obtained an average gap closed up to four times better than the default version and was able to solve 23% more problems in reduced execution times.