Interdiction Games and Monotonicity, with Application to Knapsack Problems

Matteo Fischetti (), Ivana Ljubić (), Michele Monaci () and Markus Sinnl ()
Additional contact information
Matteo Fischetti: Department of Information Engineering, University of Padua, 351200 Padua PD, Italy
Ivana Ljubić: ESSEC Business School Paris, 95021 Cergy Pontoise, France
Michele Monaci: Department of Information Engineering, University of Bologna, 40136 Bologna, Italy
Markus Sinnl: Department of Statistics and Operations Research, University of Vienna, 1090 Vienna, Austria

INFORMS Journal on Computing, 2019, vol. 31, issue 2, 390-410

Abstract: Two-person interdiction games represent an important modeling concept for applications in marketing, defending critical infrastructure, stopping nuclear weapons projects, or preventing drug smuggling. We present an exact branch-and-cut algorithm for interdiction games under the assumption that feasible solutions of the follower problem satisfy a certain monotonicity property. Prominent examples from the literature that fall into this category are knapsack interdiction, matching interdiction, and packing interdiction problems. We also show how practically relevant interdiction variants of facility location and prize-collecting problems can be modeled in our setting. Our branch-and-cut algorithm uses a solution scheme akin to Benders decomposition based on a family of so-called interdiction cuts. We present modified and lifted versions of these cuts along with exact and heuristic procedures for the separation of interdiction cuts and heuristic separation procedures for the other versions. In addition, we derive further valid inequalities and present a new heuristic procedure. We computationally evaluate the proposed algorithm on a benchmark of 360 knapsack interdiction instances from literature, including 27 instances for which the optimal solution was not known. Our approach is able to solve each of them to optimality within about one minute of computing time on a standard PC (in most cases, within just seconds), and it is up to some orders of magnitude faster than any previous approach from the literature. To further assess the effectiveness of our branch-and-cut algorithm, an additional computational study is performed on 144 randomly generated instances based on 0/1 multidimensional knapsack problems.

Keywords: interdiction games; bilevel optimization; mixed-integer optimization; branch-and-cut; multidimensional knapsack interdiction; prize-collecting interdiction (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0831 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:31:y:2019:i:2:p:390-410

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().