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.

Vai al programma dei seminari generali 2022