Preprocessing and cutting planes with conflict graphs.

Simple item page
dc.contributor.authorBrito, Samuel Souza
dc.contributor.authorSantos, Haroldo Gambini
dc.date.accessioned2022-02-08T18:11:17Z
dc.date.available2022-02-08T18:11:17Z
dc.date.issued2021pt_BR
dc.description.abstractThis 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%.pt_BR
dc.identifier.citationBRITO, 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.pt_BR
dc.identifier.doihttps://doi.org/10.1016/j.cor.2020.105176pt_BR
dc.identifier.issn0305-0548
dc.identifier.urihttp://www.repositorio.ufop.br/jspui/handle/123456789/14461
dc.identifier.uri2https://www.sciencedirect.com/science/article/abs/pii/S0305054820302938?dgcid=rss_sd_all#!pt_BR
dc.language.isoen_USpt_BR
dc.rightsrestritopt_BR
dc.subjectMixed-integer linear programmingpt_BR
dc.subjectClique inequalitiespt_BR
dc.subjectOdd-cycle inequalitiespt_BR
dc.titlePreprocessing and cutting planes with conflict graphs.pt_BR
dc.typeArtigo publicado em periodicopt_BR
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
ARTIGO_PreprocessingCuttingPlanes.pdf
Size:
1.91 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
DECOM - Artigos publicados em periódicos