Portal de Periódicos da CAPES

Artigo Produção Nacional Revisado por pares

BIBTEX RIS

Cover by disjoint cliques cuts for the knapsack problem with conflicting items

2021; Elsevier BV; Volume: 49; Issue: 6 Linguagem: Inglês

10.1016/j.orl.2021.10.001

1872-7468

Thiago Alcântara Luiz, Haroldo Gambini Santos, Eduardo Uchoa,

Optimization and Search Problems

The knapsack problem with conflicting items arises in several real-world applications. We propose a family of strong cutting planes and prove that a subfamily of these cuts can be facet-defining. Computational experiments show that the proposed cuts are very effective in reducing integrality gaps, providing dual bounds up to 78% tighter than formulations 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.