A dynamic reformulation heuristic for Generalized Interdiction Problems - Archive ouverte HAL Access content directly
Journal Articles European Journal of Operational Research Year : 2017

A dynamic reformulation heuristic for Generalized Interdiction Problems

(1) , (2) , (3, 4)
1
2
3
4

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.

Dates and versions

hal-01666298 , version 1 (18-12-2017)

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook Twitter LinkedIn More