A branch and price algorithm for a Stackelberg Security Game

Lagos, Felipe; Ordóñez, Fernando; Labbé, Martine

Document type :

Article dans une revue scientifique: Article original

DOI :

10.1016/j.cie.2017.06.034

Title :

A branch and price algorithm for a Stackelberg Security Game

Author(s) :

Lagos, Felipe [Auteur]
Georgia Institute of Technology [Atlanta]
Ordóñez, Fernando [Auteur]
Departamento de Ingenieria Industrial [Santiago] [DII]
Labbé, Martine [Auteur]
Université libre de Bruxelles [ULB]
Integrated Optimization with Complex Structure [INOCS]
Graphes et Optimisation Mathématique [Bruxelles] [GOM]

Journal title :

Computers & Industrial Engineering

Pages :

216 - 227

Publisher :

Elsevier

Publication date :

2017-09

ISSN :

0360-8352

HAL domain(s) :

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

English abstract : [en]

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 ...
Show more >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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Files

https://hal.inria.fr/hal-01666454/document
Open access
Access the document

https://hal.inria.fr/hal-01666454/document
Open access
Access the document

https://hal.inria.fr/hal-01666454/document
Open access
Access the document

document
Open access
Access the document

Lagosetal-preprint.pdf
Open access
Access the document

Lagosetal-preprint.pdf
Open access
Access the document

document
Open access
Access the document

Lagosetal-preprint.pdf
Open access
Access the document

A branch and price algorithm for a Stackelberg ... BibTeX CSV Excel RIS

Files

A branch and price algorithm for a Stackelberg ...

BibTeX

CSV

Excel

RIS