A dynamic reformulation heuristic for Generalized Interdiction Problems

Matteo Fischetti 1 Michele Monaci 2 Markus Sinnl 3, 4
3 INOCS - Integrated Optimization with Complex Structure
ULB - Université Libre de Bruxelles [Bruxelles], Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
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

https://hal.inria.fr/hal-01666298
Contributor : Markus Sinnl <>
Submitted on : Monday, December 18, 2017 - 11:10:17 AM
Last modification on : Friday, March 22, 2019 - 1:34:31 AM

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

162