Title: Exact algorithms for combinatorial interdiction problems
| Speaker: | Ricardo Fukasawa |
| Affiliation: | University of Waterloo |
| Location: | MC 5501 |
Abstract: Typical optimization paradigms involve a single decision maker that can control all variables involved. However, several practical situations involve multiple (potentially adversarial) decision makers. Bilevel optimization is a field that involves two decision makers. The key paradigm is that an upper-level decision maker acts first and after observing the upper-level decisions, a lower level decision maker optimizes their own objective. One particular important instance of such problems are so-called interdiction problems, where the upper-level decision is to try and forbid access to some decisions by the lower level and the goal of the upper level is to make the most impact into the lower-level decisions. These problems are, in general $\Sigma^P_2$-hard (likely harder than NP-hard).
In this talk I will present recent work on improving significantly on state-of-the-art exact algorithms to obtain optimal solutions to some combinatorial interdiction problems. Despite the hardness results, our algorithm can solve instances consistently in a short amount of time. We also generalize our algorithms to propose a framework that could be applied to other similar problems, by deriving relaxations based on looking at these problems as games and performing operations on such games.
This is joint work with Noah Weninger.