  We consider the Bilevel Knapsack 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 profits. The presence of two decision levels makes this
problem very difficult to solve in practice: the current state-of-the-art
algorithms can solve to optimality instances with 50-55 items at most. We
derive effective lower bounds and present a new exact approach that exploits
the structure of the induced follower's problem. The approach successfully
solves all benchmark instances within one second in the worst case and larger
instances with up to 500 items within 60 seconds.
