.png){kind=icon}
Return
The Knapsack Problem with forfeit sets
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2022.106093.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Knapsack Problem
Conflicts
Forfeit sets
Carousel Greedy
Memetic algorithm
Hybrid metaheuristic
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W
Organization
Cited Papers
.png){kind=icon}
ShareSave
ShareSaveTraces of Conflict: Environment and Eviction in British Military Training Areas, 1943 to Present
PREAI
ShareSaveShareSave
View more