Uma matheurística de melhoria para o problema da mochila com conjuntos de penalidades

Abstract

This work presents a matheuristic for the knapsack problem with forfeit sets, which is a recently introduced variant of the classic knapsack problem. The aim of this work is to evaluate the effectiveness of a known matheuristic, the Large Neighborhood Search, applied to this variant. The matheuristic combines the partial destruction of an initial solution with its optimized repair using integer linear programming. The results are compared with those obtained by an exact algorithm and the state-of-the-art, aiming to measure the quality of the generated solutions. The study demonstrates that methods like the Large Neighborhood Search can be competitive in solving more complex variants of the knapsack problem.