An exact method for binary fortification games
From MaRDI portal
Publication:6167322
DOI10.1016/J.EJOR.2022.10.038arXiv2111.13400MaRDI QIDQ6167322FDOQ6167322
Authors: Markus Leitner, Ivana Ljubić, Michele Monaci, Markus Sinnl, Kübra Tanınmış 
Publication date: 10 July 2023
Published in: European Journal of Operational Research (Search for Journal in Brave)
Abstract: A fortification game (FG) is a three-level, two-player Stackelberg game, also known as defender-attacker-defender game, in which at the uppermost level, the defender selects some assets to be protected from potential malicious attacks. At the middle level, the attacker solves an interdiction game by depreciating unprotected assets, i.e., reducing the values of such assets for the defender, while at the innermost level the defender solves a recourse problem over the surviving or partially damaged assets. Fortification games have applications in various important areas, such as military operations, design of survivable networks, protection of facilities, or power grid protection. In this work, we present an exact solution algorithm for FGs, in which the recourse problems correspond to (possibly NP-hard) combinatorial optimization problems. The algorithm is based on a new generic mixed-integer linear programming reformulation in the natural space of fortification variables. Our new model makes use of fortification cuts that measure the contribution of a given fortification strategy to the objective function value. These cuts are generated on-the-fly by solving separation problems, which correspond to (modified) middle-level interdiction games. We design a branch-and-cut-based solution algorithm based on fortification cuts, their lifted versions, and other speed-up techniques. We present a computational study using the knapsack fortification game and the shortest path fortification game. For the latter one, we include a comparison with a state-of-the-art solution method from the literature. Our algorithm outperforms this method and allows us to solve previously unsolved instances to optimality.
Full work available at URL: https://arxiv.org/abs/2111.13400
combinatorial optimizationbranch-and-cutthree-level optimizationmaximum knapsack fortificationshortest path fortification
Cites Work
- Title not available (Why is that?)
- A note on two problems in connexion with graphs
- A bilevel mixed-integer program for critical infrastructure protection planning
- Exact interdiction models and algorithms for disconnecting networks via node deletions
- A comparison of solution strategies for biobjective shortest path problems
- An exact solution approach for the interdiction median problem with fortification
- Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
- Shortest-path network interdiction
- An analytical approach to the protection planning of a rail intermodal terminal network
- Optimizing dynamic investment decisions for railway systems protection
- Survivable network design under optimal and heuristic interdiction scenarios
- A class of algorithms for mixed-integer bilevel min-max optimization
- A branch-and-cut algorithm for the edge interdiction clique problem
- Bilevel programming and the separation problem
- A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation
- Algorithms for network interdiction and fortification games
- A new general-purpose algorithm for mixed-integer bilevel linear programs
- A projection-based reformulation and decomposition algorithm for global optimization of a class of mixed integer bilevel linear programs
- The multi-terminal maximum-flow network-interdiction problem
- A Backward Sampling Framework for Interdiction Problems with Fortification
- A study on the computational complexity of the bilevel knapsack problem
- Interdiction Games and Monotonicity, with Application to Knapsack Problems
- The maximum clique interdiction problem
- Bilevel knapsack with interdiction constraints
- On the use of intersection cuts for bilevel optimization
- On integer and bilevel formulations for the \(k\)-vertex cut problem
- An exact approach for the bilevel knapsack problem with interdiction constraints and extensions
- A survey of network interdiction models and algorithms
- Multilevel approaches for the critical node problem
- Tri-level mixed-binary linear programming: solution approaches and application in defending critical infrastructure
- A survey on mixed-integer programming techniques in bilevel optimization
- Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem
- Complexity of the multilevel critical node problem
- Improved \(x\)-space algorithm for min-max bilevel problems with an application to misinformation spread in social networks
- An exact algorithm for solving the bilevel facility interdiction and fortification problem
- Integer programming methods for solving binary interdiction games
- A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games
- A Branch-and-Cut Algorithm for Submodular Interdiction Games
Cited In (1)
This page was built for publication: An exact method for binary fortification games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6167322)
