We consider the bilevel knapsack problem with interdiction constraints, an extension of the classic 0–1 knapsack problem formulated as a Stackelberg game with two agents, a leader and a follower, that choose items from a common set and hold their own private knapsacks. First, the leader selects some items to be interdicted for the follower while satisfying a capacity constraint. Then the follower packs a set of the remaining items according to his knapsack constraint in order to maximize the profits. The goal of the leader is to minimize the follower’s total profit. We derive effective lower bounds for the bilevel knapsack problem and present an exact method that exploits the structure of the induced follower’s problem. The approach strongly outperforms the current state-of-the-art algorithms designed for the problem. We extend the same algorithmic framework to the interval min–max regret knapsack problem after providing a novel bilevel programming reformulation. Also for this problem, the proposed approach outperforms the exact algorithms available in the literature.

An exact approach for the bilevel knapsack problem with interdiction constraints and extensions / Della Croce, F.; Scatamacchia, R.. - In: MATHEMATICAL PROGRAMMING. - ISSN 0025-5610. - 183:1-2(2020), pp. 249-281. [10.1007/s10107-020-01482-5]

An exact approach for the bilevel knapsack problem with interdiction constraints and extensions

Della Croce F.;Scatamacchia R.
2020

Abstract

We consider the bilevel knapsack problem with interdiction constraints, an extension of the classic 0–1 knapsack problem formulated as a Stackelberg game with two agents, a leader and a follower, that choose items from a common set and hold their own private knapsacks. First, the leader selects some items to be interdicted for the follower while satisfying a capacity constraint. Then the follower packs a set of the remaining items according to his knapsack constraint in order to maximize the profits. The goal of the leader is to minimize the follower’s total profit. We derive effective lower bounds for the bilevel knapsack problem and present an exact method that exploits the structure of the induced follower’s problem. The approach strongly outperforms the current state-of-the-art algorithms designed for the problem. We extend the same algorithmic framework to the interval min–max regret knapsack problem after providing a novel bilevel programming reformulation. Also for this problem, the proposed approach outperforms the exact algorithms available in the literature.
File in questo prodotto:
File Dimensione Formato  
Final_Revised_mathprog.pdf

embargo fino al 26/02/2021

Tipologia: 2. Post-print / Author's Accepted Manuscript
Licenza: PUBBLICO - Tutti i diritti riservati
Dimensione 424.73 kB
Formato Adobe PDF
424.73 kB Adobe PDF Visualizza/Apri
DellaCroce-Scatamacchia2020_Article_AnExactApproachForTheBilevelKn.pdf

non disponibili

Tipologia: 2a Post-print versione editoriale / Version of Record
Licenza: Non Pubblico - Accesso privato/ristretto
Dimensione 434.91 kB
Formato Adobe PDF
434.91 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11583/2876215