The Knapsack Problem with forfeit sets. (March 2023)

• Record Type: Journal Article
• Authors: D'Ambrosio, Ciriaco; Laureana, Federica; Raiconi, Andrea; Vitale, Gaetano
• Is Part Of: Computers & operations research. Volume 151(2023)
• Publication Date: 2023-03
• Subjects: Knapsack Problem -- Conflicts -- Forfeit sets -- Carousel Greedy -- Memetic algorithm -- Hybrid metaheuristic; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.106093
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: This work introduces a novel extension of the 0/1 Knapsack Problem in which we consider the existence of so-called forfeit sets. A forfeit set is a subset of items of arbitrary cardinality, such that including a number of its elements that exceeds a predefined allowance threshold implies some penalty costs to be paid in the objective function value. A global upper bound on these allowance violations is also considered. We show that the problem generalizes both the Knapsack Problem with conflicts among item pairs and the Knapsack Problem with forfeit pairs, that have been previously introduced in the literature. We present a polynomial subcase by proving the integrality of its LP relaxation polytope and, we introduce three heuristic approaches, namely a constructive greedy, an algorithm based on the recently introduced Carousel Greedy paradigm and a hybrid Memetic/Carousel Greedy algorithm. Finally, we validate the performances for the proposed algorithms on a set of benchmark instances that consider both random and correlated data. Highlights: A novel variant of the Knapsack Problem with penalty costs is proposed. Costs occur when items belonging to certain subsets are taken together. We generalize the Knapsack Problem with Conflicts and Knapsack Problem with Forfeits. A metaheuristic combining Memetic Algorithm with Carousel Greedy is proposed.