Coordinated defender strategies for border patrols

Bucarey, Víctor; Casorrán, Carlos; Labbé, Martine; Ordóñez, Fernando; Figueroa, Oscar

Type de document :

Compte-rendu et recension critique d'ouvrage

Titre :

Coordinated defender strategies for border patrols

Auteur(s) :

Bucarey, Víctor [Auteur]
Departamento de Ingenieria Industrial [Santiago] [DII]
Casorrán, Carlos [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Labbé, Martine [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Ordóñez, Fernando [Auteur]
Departamento de Ingenieria Industrial [Santiago] [DII]
Figueroa, Oscar [Auteur]

Titre de la revue :

European Journal of Operational Research

Éditeur :

Elsevier

Date de publication :

2021

ISSN :

0377-2217

Mot(s)-clé(s) en anglais :

Stackelberg games
Matching polyhedra
Security application

Discipline(s) HAL :

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

Résumé en anglais : [en]

An effective patrol of a large area can require the coordinated action of diverse security resources. In this work we formulate a Stackelberg Security game that coordinates such resources in a border patrol problem. In ...
Lire la suite >An effective patrol of a large area can require the coordinated action of diverse security resources. In this work we formulate a Stackelberg Security game that coordinates such resources in a border patrol problem. In this security domain, resources from different precincts have to be paired to conduct patrols in the border due to logistic constraints. Given this structure the set of pure defender strategies is of exponential size. We describe the set of mixed strategies using a polynomial number of variables but exponentially many constraints that come from the matching polytope. We then include this description in a mixed integer formulation to compute the Strong Stackelberg Equilibrium efficiently with a branch and cut scheme. Since the optimal patrol solution is a probability distribution over the set of exponential size, we also introduce an efficient sampling method that can be used to deploy the security resources every shift. Our computational results evaluate the efficiency of the branch and cut scheme developed and the accuracy of the sampling method. We show the applicability of the methodology by solving a real world border patrol problem.Lire moins >

Langue :

Anglais

Vulgarisation :

Non

Collections :