Conflict graphs in mixed-integer linear programming : preprocessing, heuristics and cutting planes.

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorSantos, Haroldo Gambini-
Autor(es): dc.contributorSantos, Haroldo Gambini-
Autor(es): dc.contributorFonseca, George Henrique Godim da-
Autor(es): dc.contributorMateus, Geraldo Robson-
Autor(es): dc.contributorAragão, Marcus Vinicius Soledade Poggi de-
Autor(es): dc.contributorToffolo, Túlio Ângelo Machado-
Autor(es): dc.creatorBrito, Samuel Souza-
Data de aceite: dc.date.accessioned2025-08-21T15:19:01Z-
Data de disponibilização: dc.date.available2025-08-21T15:19:01Z-
Data de envio: dc.date.issued2020-06-25-
Data de envio: dc.date.issued2020-06-25-
Data de envio: dc.date.issued2019-
Fonte completa do material: dc.identifierhttp://www.repositorio.ufop.br/handle/123456789/12386-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/1010211-
Descrição: dc.descriptionPrograma 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.-
Descrição: dc.descriptionThis 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%.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languageen-
Direitos: dc.rightsaberto-
Direitos: dc.rightsAn error occurred getting the license - uri.-
Direitos: dc.rightsAutorização concedida ao Repositório Institucional da UFOP pelo(a) autor(a) em 17/06/2020 com as seguintes condições: disponível sob Licença Creative Commons 4.0 que permite copiar, distribuir e transmitir o trabalho desde que sejam citados o autor e o licenciante. Não permite o uso para fins comerciais.-
Palavras-chave: dc.subjectProgramação linear-
Palavras-chave: dc.subjectHeurística-
Palavras-chave: dc.subjectProgramação - computadores - processamento-
Palavras-chave: dc.subjectProgramação heurística-
Título: dc.titleConflict graphs in mixed-integer linear programming : preprocessing, heuristics and cutting planes.-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositório Institucional - UFOP

Não existem arquivos associados a este item.