Benders Decomposition based algorithms for general and security stackelberg games

Abstract

Los juegos de Stackelberg modelan situaciones donde existe más de un tomador de decisiones en una interaccion líder-seguidor, donde el líder toma una decisión en primer lugar y luego lo hace el seguidor. Cuando esto ocurre en un contexto de seguridad, con el líder actuando como defensor y el seguidor como atacante, se llama juego de seguridad de Stackelberg. Los juegos de Stackelberg son ampliamente usados para aplicaciones en economía, transportes, biología, finanzas, seguridad, entre otros. Debido al uso de los juegos de Stackelberg generales y de seguridad en aplicaciones del mundo real, se ha vuelto importante resolver estos problemas en forma eficiente. De esta forma, los usuarios pueden tomar decisiones cuando lo requieran, cada día o cada hora. Esta necesidad de eficiencia ha producido diferentes formulaciones y métodos de solución. En esta tesis contribuimos al trabajo en formulaciones enteras mixtas de juegos de Stackelberg y algoritmos de descomposición para resolverlos. Específicamente, consideramos cortes de Benders generados de la formulación fuerte, y cortes de Benders normalizados como fue presentado por [29]. Por esta razón, esta tesis está enfocada en el desempeño de algoritmos. La investigación reciente ha estudiado la eficiencia de diferentes formulaciones enteras mixtas para juegos de Stackelberg, incluyendo seguridad. Un hallazgo importante es que la formulación con el menor gap de integralidad, que considera más variables y restricciones, es la que tiene la relajación lineal más difícil de resolver. Este intercambio hace difícil decidir qué formulación es preferible para resolver instancias específicas, y sugiere fortalecer la formulación débil (FD) con cortes de la formulación fuerte (FF). Este trabajo estudia el uso de cortes de Benders en la FD que son generados por la FF. En particular, investigamos el efecto de diferentes métodos de regularización, el uso de cortes de Benders normalizados, y la elección de si generar cortes solo en el nodo raíz o en todo el árbol branch & bound. Nuestros resultados computacionales consideran cuatro algoritmos para cada tipo de juego de Stackelberg, general y seguridad. La variación más interesante que estudiamos está basada en la normalización de la descomposición de Benders, cuyo objetivo es reducir el numero de cortes de optimalidad y factibilidad, y reemplazarlos por solo un tipo de corte, al que llamamos corte normalizado. Concluimos que cut & branch, con variables en R en el problema maestro y estabilización, supera a los otros métodos considerados en todas las instancias. Se sugiere oportunidades para mejorar estas estrategias de descomposición en investigaciones futuras.