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
D'Ambrosio C.;Raiconi A.
;Vitale G.;
2022
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.File | Dimensione | Formato | |
---|---|---|---|
Forfeits_SOCO_IRIS_accepted_version.pdf
Open Access dal 28/10/2022
Tipologia:
Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza:
Copyright dell'editore
Dimensione
724.36 kB
Formato
Adobe PDF
|
724.36 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.