Presentation on YouTube.

While several optimization problems consider that there is a single decision-maker involved, interdiction problems are a form of Stackelberg game where there are two decision-makers involved: a leader and a follower. The follower follows a “classical” optimization problem, trying to optimize a given objective subject to some constraints. The leader is allowed to interdict/block items that are available to the follower, with the goal to make the follower’s objective as bad as possible. This form of zero-sum game can be significantly harder than the original classical counterparts, both in terms of complexity class and in terms of exact algorithm performance.

We study two variants of this problem, with the assumption that the leader must satisfy a knapsack constraint. The different variants relate to the problem the follower solves: knapsack and minimum spanning tree.

The algorithms we develop are based on branch-and-bound with a carefully devised bounding scheme. They improve significantly (by orders of magnitude) the limits of exact algorithms for these problems and show that there is much that can be further researched in this area.

This is joint work with Noah Weninger.

Short bio: Ricardo Fukasawa is a Professor at the Department of Combinatorics and Optimization of the University of Waterloo. He did his undergrad and Masters in Electrical Engineering at PUC-Rio, Brazil. He worked at GAPSO Inc developing optimization software for Logistics applications for three years before starting his PhD. He finished his PhD in Algorithms, Combinatorics and Optimization at GeorgiaTech in 2008, under the supervision of Bill Cook. He was the recipient of the 2008-2009 IBM Herman Goldstine postdoctoral fellowship and an Early Research Award from the ministry of colleges and universities in Ontario. He is currently on the editorial board of Mathematical Programming Computation, Operations Research Letters, RAIRO-OR and INFOR. His research interests are in theory and computations for exact algorithms for hard discrete optimization problems. He has works in stochastic programming, bilevel programming, vehicle routing and general mixed-integer programming, as well as works on many applications.