Preprocessing and Cutting Planes with Conflict Graphs

DOI10.1016/J.COR.2020.105176arXiv1909.07780MaRDI QIDQ6325473FDOQ6325473

Haroldo G. Santos, Samuel Souza Brito

Publication date: 17 September 2019

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\mathrm{\%}$ 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\mathrm{\%}$.

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Mixed integer programming (90C11)

This page was built for publication: Preprocessing and Cutting Planes with Conflict Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6325473)