.png){kind=icon}
返回
The Knapsack Problem with forfeit sets
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2022.106093.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
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.
Keyword:
Knapsack Problem
Conflicts
Forfeit sets
Carousel Greedy
Memetic algorithm
Hybrid metaheuristic
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
引用论文
.png){kind=icon}
分享收藏The Clinical and Pathological Effects of Serum C3 Level and Mesangial C3 Intensity in Patients with IgA NephropathyIgA肾病患者的血清C3水平和系膜C3强度及其临床与病理效应
OAAI
OAAI分享收藏Traces of Conflict: Environment and Eviction in British Military Training Areas, 1943 to Present
PREAI
分享收藏
查看更多内容