Please use this identifier to cite or link to this item:
Title: Preprocessing and cutting planes with conflict graphs.
Authors: Brito, Samuel Souza
Santos, Haroldo Gambini
Keywords: Mixed-integer linear programming
Clique inequalities
Odd-cycle inequalities
Issue Date: 2021
Citation: 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: <!>. Acesso em: 25 ago. 2021.
Abstract: 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%.
ISSN: 0305-0548
Appears in Collections:DECOM - Artigos publicados em periódicos

Files in This Item:
File Description SizeFormat 
  Restricted Access
1,95 MBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.