A dynamic reformulation heuristic for Generalized Interdiction Problems

Fischetti, Matteo; Monaci, Michele; Sinnl, Markus

Type de document :

Article dans une revue scientifique: Article original

DOI :

10.1016/j.ejor.2017.11.043

Titre :

A dynamic reformulation heuristic for Generalized Interdiction Problems

Auteur(s) :

Fischetti, Matteo [Auteur]
Dipartimento di Ingegneria de l'Informazione [Padova] [DEI]
Monaci, Michele [Auteur]
Department of electrical, electronic and information engineering "GUGLIELMO MARCONI" [Bologna] [DEI]
Sinnl, Markus [Auteur]
Universität Wien = University of Vienna
Integrated Optimization with Complex Structure [INOCS]

Titre de la revue :

European Journal of Operational Research

Pagination :

1-12

Éditeur :

Elsevier

Date de publication :

2017-11

ISSN :

0377-2217

Discipline(s) HAL :

Computer Science [cs]/Operations Research [math.OC]

Résumé en anglais : [en]

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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :