Skip to Main content Skip to Navigation
Journal articles

A dynamic reformulation heuristic for Generalized Interdiction Problems

Abstract : We consider a subfamily of mixed-integer linear bilevel problems that we call Generalized Interdiction Problems. This class of problems includes, among others, the widely-studied interdiction problems, i.e., zero-sum Stackelberg games where two players (called the leader and the follower) share a set of items, and the leader can interdict the usage of certain items by the follower. Problems of this type can be modeled as Mixed-Integer Nonlinear Programming problems, whose exact solution can be very hard. In this paper we propose a new heuristic scheme based on a single-level and compact mixed-integer linear programming reformulation of the problem obtained by relaxing the integrality of the follower variables. A distinguished feature of our method is that general-purpose mixed-integer cutting planes for the follower problem are exploited, on the fly, to dynamically improve the reformulation. The resulting heuristic algorithm proved very effective on a large number of test instances, often providing an (almost) optimal solution within very short computing times.
Document type :
Journal articles
Complete list of metadatas
Contributor : Markus Sinnl <>
Submitted on : Monday, December 18, 2017 - 11:10:17 AM
Last modification on : Tuesday, September 29, 2020 - 12:24:14 PM

Links full text




Matteo Fischetti, Michele Monaci, Markus Sinnl. A dynamic reformulation heuristic for Generalized Interdiction Problems. European Journal of Operational Research, Elsevier, 2017, pp.1-12. ⟨10.1016/j.ejor.2017.11.043⟩. ⟨hal-01666298⟩



Record views