Cover by disjoint clique cuts and machine learning to assist mixed-integer linear programming solvers.

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorSouza, Marcone Jamilson Freitas-
Autor(es): dc.contributorToffolo, Túlio Ângelo Machado-
Autor(es): dc.contributorSouza, Marcone Jamilson Freitas-
Autor(es): dc.contributorToffolo, Túlio Ângelo Machado-
Autor(es): dc.contributorPenna, Puca Huachi Vaz-
Autor(es): dc.contributorSá, Elisangela Martins de-
Autor(es): dc.contributorSubramanian, Anand-
Autor(es): dc.contributorSantos, Haroldo Gambini-
Autor(es): dc.creatorLuiz, Thiago Alcântara-
Data de aceite: dc.date.accessioned2025-08-21T15:44:02Z-
Data de disponibilização: dc.date.available2025-08-21T15:44:02Z-
Data de envio: dc.date.issued2025-08-05-
Data de envio: dc.date.issued2024-
Fonte completa do material: dc.identifierhttps://www.repositorio.ufop.br/handle/123456789/20723-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/1022809-
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.descriptionCutting planes and primal heuristics are two of the most important components of mod- ern mixed-integer linear programming (MILP) solvers. To improve both the strength of MILP formulations and the process of identifying feasible integer solutions, this thesis presents two key contributions. First, we propose a family of strong cutting planes for the knapsack problem with conflicting items and prove that a subfamily of these cuts can be facet-defining. The computational experiments demonstrate that the proposed cuts effectively reduce integrality gaps, providing dual bounds up to 78% tighter than formu- lations strengthened with traditional combinatorial cuts. We also show that it is possible to adapt a recently proposed lifting procedure to further strengthen the proposed cuts. Second, we propose a machine learning-based recommendation system that identifies the most suitable diving heuristic (a type of primal heuristic) and whether it should be com- bined with cutting planes and/or feasibility pump. These recommendations are based on 207 features extracted from the MILP problem. The computational results show that the recommendation system leads to the discovery of feasible solutions in 87% of the possi- ble cases. This corresponds to 10% more feasible integer solutions than the best diving heuristic combined with feasibility pump and cutting planes, while requiring only 52% of the total runtime.-
Descrição: dc.descriptionPlanos de corte e heurísticas primais estão entre os componentes mais importantes dos resolvedores modernos de programação linear inteira mista (PLIM). Com o objetivo de fortalecer as formulações de PLIM e aprimorar o processo de identificação de soluções inteiras factíveis, esta tese apresenta duas contribuições principais. Primeiramente, propõe-se uma família de planos de corte fortes para o problema da mochila com itens conflitantes, demonstrando que uma subfamília desses cortes pode definir facetas. Os experimentos computacionais mostram que os cortes propostos reduzem efetivamente os gaps de integralidade, fornecendo limites duais até 78% mais apertados do que as formulações fortalecidas com cortes combinatórios tradicionais. Também demonstramos que é possível adaptar um procedimento de levantamento recentemente proposto para reforçar ainda mais os cortes propostos. Em segundo lugar, propomos um sistema de recomendação baseado em aprendizado de máquina que identifica a heurística de mergulho (um tipo de heurística primal) mais adequada e se ela deve ser combinada com planos de corte e/ou bomba de viabilidade. Essas recomendações são baseadas em 207 características extraídas do problema de PLIM. Os resultados computacionais indicam que o sistema de recomendação leva à descoberta de soluções factíveis em 87% dos casos possíveis, o que representa um aumento de 10% em relação à melhor heurística de mergulho combinada com bomba de viabilidade e planos de corte, além de exigir apenas 52% do tempo total de execução.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languageen-
Direitos: dc.rightsaberto-
Direitos: dc.rightsAttribution-NonCommercial-NoDerivs 3.0 United States-
Direitos: dc.rightshttp://creativecommons.org/licenses/by-nc-nd/3.0/us/-
Direitos: dc.rightsAutorização concedida ao Repositório Institucional da UFOP pelo(a) autor(a) em 30/07/2025 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 nem a adaptação.-
Palavras-chave: dc.subjectOtimização matemáticca-
Palavras-chave: dc.subjectHeurística-
Palavras-chave: dc.subjectAprendizado de máquina-
Palavras-chave: dc.subjectProgramação linear-
Título: dc.titleCover by disjoint clique cuts and machine learning to assist mixed-integer linear programming solvers.-
Título: dc.titleCortes de cobertura por cliques disjuntas e aprendizado de máquina para auxiliar resolvedores de programação linear inteira mista.-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositório Institucional - UFOP

Não existem arquivos associados a este item.