A GRASP Heuristic with Path-Relinking for the Knapsack Problem with Forfeits

In this work, we explore a variant of the traditional Knapsack Problem, known as the Knapsack Problem with Forfeits. In this version, a set composed of pairs of distinct items, known as forfeit pairs, is added. Each pair consists of items whose simultaneous selection in the solution results in an increase in penalty to the total solution cost. We present a heuristic approach based on GRASP with Path-relinking to solve this problem. The results obtained reveal that our heuristic outperforms other approaches in the literature, achieving an average gap of less than 1% on the evaluated instances.