A branch and price algorithm for a Stackelberg Security Game

Felipe Lagos 1 Fernando Ordóñez 2 Martine Labbé 3, 4, 5
4 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 : Mixed integer optimization formulations are an attractive alternative to solve Stackelberg Game problems thanks to the efficiency of state of the art mixed integer algorithms. In particular, decomposition algorithms, such as branch and price methods, make it possible to tackle instances large enough to represent games inspired in real world domians. In this work we focus on Stackelberg Games that arise from a security application and investigate the use of a new branch and price method to solve its mixed integer optimization formulation. We prove that the algorithm provides upper and lower bounds on the optimal solution at every iteration and investigate the use of stabilization heuristics. Our preliminary computational results compare this solution approach with previous decomposition methods obtained from alternative integer programming formulations of Stackelberg games.
Type de document :
Article dans une revue
Computers & Industrial Engineering, 2017, 111, pp.216 - 227. 〈10.1016/j.cie.2017.06.034〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01666454
Contributeur : Bernard Fortz <>
Soumis le : jeudi 21 décembre 2017 - 14:27:33
Dernière modification le : mardi 3 juillet 2018 - 11:34:55

Fichier

Lagosetal-preprint.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Felipe Lagos, Fernando Ordóñez, Martine Labbé. A branch and price algorithm for a Stackelberg Security Game. Computers & Industrial Engineering, 2017, 111, pp.216 - 227. 〈10.1016/j.cie.2017.06.034〉. 〈hal-01666454〉

Partager

Métriques

Consultations de la notice

196

Téléchargements de fichiers

52