Go to JKU Homepage
Institute of Production and Logistics Management
What's that?

Institutes, schools, other departments, and programs create their own web content and menus.

To help you better navigate the site, see here where you are at the moment.

Detail

Paper by K. Taninmis (PLM), M. Sinnl (PLM) accepted for publication@VHB A journal

The paper titled "A Branch-and-Cut Algorithm for Submodular Interdiction Games" by Kübra Taninmis and Markus Sinnl (both at the Institute of Production and Logistics Management) has been accepted for publication at INFORMS Journal about Computing.

Abstract:

Many relevant applications from diverse areas such as marketing, wildlife conservation, and defending critical infrastructure can be modeled as interdiction games. In this work, we introduce interdiction games whose objective is a monotone and submodular set function. Given a ground set of items, the leader interdicts the usage of some of the items of the follower in order to minimize the objective value achievable by the follower, who seeks to maximize a submodular set function over the uninterdicted items subject to knapsack constraints. We propose an exact branch-and-cut algorithm for this kind of interdiction game. The algorithm is based on interdiction cuts, which allow the leader to capture the follower’s objective function value for a given interdiction decision of the leader and exploit the submodularity of the objective function. We also present extensions and liftings of these cuts and discuss additional preprocessing procedures. We test our solution framework on the weighted maximal covering interdiction game and the bipartite inference interdiction game. For both applications, the improved variants of our interdiction cut perform significantly better than the basic version. For the weighted maximal covering interdiction game for which a mixed-integer bilevel linear programming (MIBLP) formulation is available, we compare the results with those of a state-of-the-art MIBLP solver. Whereas the MIBLP solver yields a minimum of 54% optimality gap within one hour, our best branch-and-cut setting solves all but four of 108 instances to optimality with a maximum of 3% gap among unsolved ones.