Conflict graphs in mixed-integer linear programming : preprocessing, heuristics and cutting planes.
No Thumbnail Available
Date
2020
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This thesis addresses the development of con ict graph-based algorithms for MixedInteger Linear Programming, including: (i) an e cient infrastructure for the construction and manipulation of con ict 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; (iv) an odd-cycle cut separator with a new lifting module to produce valid odd-wheel inequalities; (v) two diving heuristics capable of generating integer
feasible solutions in restricted execution times. Additionally, we generated a new version
of the COIN-OR Branch-and-Cut (CBC) solver by including our con ict graph infrastructure, preprocessing routine and cut separators. 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%.
Description
Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto.
Keywords
Programação linear, Heurística, Programação - computadores - processamento, Programação heurística
Citation
BRITO, Samuel Souza. Conflict graphs in mixed-integer linear programming: preprocessing, heuristics and cutting planes. 110 f. 2020. Tese (Doutorado em Ciência da Computação) - Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto, Ouro Preto, 2020.