In this paper, we present a novel hybrid metaheuristic for the Knapsack Problem with Forfeits (KPF). KPF is a recently introduced generalization of the Knapsack Problem. In this variant, a penalty cost incurs whenever both items composing a so-called forfeit pair belong to the solution. Our proposed algorithm, called GA-CG Forfeits, combines the strengths of the Genetic and Carousel Greedy paradigms. In this work, we define the algorithm and compare it with two previously proposed heuristics on a set of benchmark instances. In these tests, GA-CG Forfeits provided significantly better solutions than the other two algorithms on all instances.
A hybrid metaheuristic for the Knapsack Problem with Forfeits
Capobianco, G;D'Ambrosio, C;Pavone, L;Vitale, G;
2022-01-01
Abstract
In this paper, we present a novel hybrid metaheuristic for the Knapsack Problem with Forfeits (KPF). KPF is a recently introduced generalization of the Knapsack Problem. In this variant, a penalty cost incurs whenever both items composing a so-called forfeit pair belong to the solution. Our proposed algorithm, called GA-CG Forfeits, combines the strengths of the Genetic and Carousel Greedy paradigms. In this work, we define the algorithm and compare it with two previously proposed heuristics on a set of benchmark instances. In these tests, GA-CG Forfeits provided significantly better solutions than the other two algorithms on all instances.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
