The 0/1 Knapsack Problem is one of the most well-known problems in combinatorial optimization, with multiple applications including capital budgeting, loading of goods in transport vehicles, and assignment of tasks or resources, among others. In this presentation we introduce a novel variant of the problem called Knapsack Problem with Forfeit Sets (KPFS), which considers a collection of possibly overlapping sets of items (forfeit sets), representing contrasting choiches. Each set has an associated allowance threshold and a penalty cost. The allowance threshold defines how many items can be chosen from each set before paying, in the objective function, the associated cost. A global limit on the number of allowed threshold violations is also considered. We show the problem to generalize two previously proposed variants of the 0/1 Knapsack Problem, and present a polynomially solvable subcase. Finally, we propose three heuristic and metaheuristic approaches to face the problem and present some computational results.
