Bilevel Knapsack with interdiction constraints

A. Caprara, M. Carvalho, A. Lodi, G.J. Woeginger

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

19 Citaten (Scopus)
1 Downloads (Pure)


We consider a bilevel integer programming model that extends the classic 0-1 knapsack problem in a very natural way. The model describes a Stackelberg game where the leader's decision interdicts a subset of the knapsack items for the follower. As this interdiction of items substantially increases the difficulty of the problem, it prevents the application of the classical methods for bilevel programming and of the specialized approaches that are tailored to other bilevel knapsack variants. Motivated by the simple description of the model, by its complexity, by its economic applications, and by the lack of algorithms to solve it, we design a novel viable way for computing optimal solutions. Finally, we present extensive computational results that show the effectiveness of the new algorithm on instances from the literature and on randomly generated instances.

Originele taal-2Engels
Pagina's (van-tot)319-333
Aantal pagina's15
TijdschriftINFORMS Journal on Computing
Nummer van het tijdschrift2
StatusGepubliceerd - 1 mrt 2016

Vingerafdruk Duik in de onderzoeksthema's van 'Bilevel Knapsack with interdiction constraints'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit