Recovering Beam Search for the 0-1 Knapsack Problem with Forfeits

The Knapsack Problem is one of the well-known problems in the field of combinatorial optimization, studied for over a century. It is a problem with a very intuitive construction, but it has numerous applications in various fields such as cryptography. There are several variants of this problem, such as the 0-1 Knapsack Problem, the Multidimensional Knapsack Problem, and others. In this thesis, our goal is to develop a solution for the 0-1 Knapsack Problem with Forfeits (or Penalties). This problem is a particular case of the 0-1 Knapsack Problem in which there is a reduction in profit when certain pairs of items are taken into the knapsack. This problem is difficult to solve, as it belongs to the class of NP-Hard problems. A heuristic solution based on Recovering Beam Search will be presented, with an approach to estimate an upper bound at each explored node based on Dynamic Programming. Initially, a description of the relevant theory to the algorithm will be provided, followed by a detailed description of the problem, and finally, our solution will be presented, including computational results.