Preprocessing and cutting planes with conflict graphs.
Nenhuma Miniatura disponível
Data
2021
Título da Revista
ISSN da Revista
Título de Volume
Editor
Resumo
This paper addresses the development of conflict graph-based algorithms and data structures into the COIN-OR Branch-and-Cut (CBC) solver, including: ð Þi an efficient infrastructure for the construction and manipulation of conflict graphs; ð Þii a preprocessing routine based on a clique strengthening scheme that can both reduce the number of constraints and produce stronger formulations; ð Þ iii a clique cut separator capable of obtaining dual bounds at the root node LP relaxation that are 19:65% stronger than those 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; and ð Þ iv an odd-cycle cut separator with a new lifting module to produce valid odd-wheel inequalities. The average gap closed by this new version of CBC was up to four times better than its previous version. Moreover, the number of mixed-integer programs solved by CBC in a time limit of three hours was increased by 23:53%.
Descrição
Palavras-chave
Mixed-integer linear programming, Clique inequalities, Odd-cycle inequalities
Citação
BRITO, S. S.; SANTOS, H. G. Preprocessing and cutting planes with conflict graphs. Computers and Operations Research, v. 128, p. 105-176, 2021. Disponível em: <https://www.sciencedirect.com/science/article/abs/pii/S0305054820302938?dgcid=rss_sd_all#!>. Acesso em: 25 ago. 2021.