Conference/Workshop of interest for AIROYoungers

From: 19 Jan 2022
To: 19 Jan 2022
IAC, CNR (online)
Inaugura la nuova stagione 2022 dei seminari generali dell'IAC Andrea Raiconi, ricercatore dell'istituto IAC–CNR.

Il 19 gennaio alle 14.30 si svolgerà il primo dei seminari generali dell'IAC per l'anno 2022. Andrea Raiconi, ricercatore IAC nella sede di Napoli, presenterà un lavoro dal titolo: The Knapsack Problem with Forfeit Sets.

Di seguito l'abstract del seminario (che si svolgerà in italiano).

The 0/1 Knapsack Problem is one of the most well-known problems in combinatorial optimization, with multiple applications including capital budgeting, loading of goods in transport vehicles, and assignment of tasks or resources, among others.
In this presentation, we introduce a novel variant of the problem called Knapsack Problem with Forfeit Sets (KPFS), which considers a collection of possibly overlapping sets of items (forfeit sets), representing contrasting choices. Each set has an associated allowance threshold and a penalty cost. The allowance threshold defines how many items can be chosen
from each set before paying, in the objective function, the associated cost. A global limit on the number of allowed threshold violations is also considered. We show the problem to generalize two previously proposed variants of the 0/1 Knapsack Problem, and present a polynomially solvable subcase. Finally, we propose three heuristic and metaheuristic approaches to face the problem and present some computational results.

Il seminario sarà trasmesso in streaming sul canale YouTube dell'IAC @CNR IAC.