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

Este documento apresenta as principais contribuições da tese de doutorado de Samuel Souza Brito. A tese aborda o desenvolvimento de algoritmos baseados em grafos de conflitos para Programação Linear Inteira Mista, incluindo: (i) uma rotina de preprocessamento que reduz o número de restrições e produz automaticamente formulações mais fortes; (ii) um separador de cortes clique que produz limites duais mais fortes do que aqueles providos pelos geradores equivalentes dos resolvedores CPLEX, CBC e GLPK; (iii) um separador de cortes de ciclo-ímpar com uma nova rotina de lifting; (iv) uma infraestrutura eficiente para construir e manipular grafos de conflitos; e (v) duas heurísticas diving que geram soluções viáveis em tempos de execução restritos. Uma nova versão do CBC foi criada, incluindo esses algoritmos baseados em grafos de conflitos. A média do gap fechado por essa nova versão foi até quatro vezes melhor e o número de problemas resolvidos aumentou em 23.53%.