Determining the Best Algorithm for the Knapsack Problem with Forfeits

In 2024, four papers that presented four different solution approaches for the knapsack problem with forfeits (KPF) appeared in the OR literature. However, none of these four solution approaches compared their performance to the other three on a standard set of 120 KPF test instances. In this short paper, both empirically and statistically, these four KPF solution approaches are compared. Furthermore, by using the solutions from the best method (HESM) among the four to initialize Gurobi, bounded solutions are obtained. For the 120 KPF test instances, this simple hybrid approach resulted in solutions that, on average, were guaranteed to be within 7% of the optimums. This type of guarantee does not exist for other KPF solution methods in the literature. It is very important for operations research (OR) practitioners that need to ensure the value of their solutions to management to have some guarantee of the quality of these solutions.