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.
Type de document :
Article dans une revue
European Journal of Operational Research, Elsevier, 2017, pp.1-12. 〈10.1016/j.ejor.2017.11.043〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01666298
Contributeur : Markus Sinnl <>
Soumis le : lundi 18 décembre 2017 - 11:10:17
Dernière modification le : jeudi 11 janvier 2018 - 06:27:32

Identifiants

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〉

Partager

Métriques

Consultations de la notice

23