Videos

A fast combinatorial algorithm for the bilevel knapsack interdiction problem

Presenter
February 28, 2023
Abstract
The single-level (classical) knapsack problem consists of picking a subset of n items maximizing profit, subject to a budget (knapsack) constraint. In the bilevel knapsack interdiction problem, there are two levels of decision-makers. The lower-level decision maker is attempting to solve the classical knapsack problem. The upper-level decision maker has the goal of minimizing the profit of the lower-level decision maker, by picking items that will be then unavailable. The upper-level has its own (independent) knapsack constraint to satisfy too. Previous approaches to this problem were based on using MIP solvers. We develop a branch-and-bound algorithm for the problem that relies on a strong lower bound and specialized branching, using combinatorial arguments. Our approach improves on the previous best approaches by up to two orders of magnitude in our test instances, significantly increasing the size of instances that can be consistently solved to optimality. This is joint work with Noah Weninger.
Supplementary Materials