An exact method for binary fortification games
From MaRDI portal
Publication:6167322
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.
Cites work
- scientific article; zbMATH DE number 2107164 (Why is no real title available?)
- A Backward Sampling Framework for Interdiction Problems with Fortification
- A Branch-and-Cut Algorithm for Submodular Interdiction Games
- A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games
- A bilevel mixed-integer program for critical infrastructure protection planning
- A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation
- A branch-and-cut algorithm for the edge interdiction clique problem
- A class of algorithms for mixed-integer bilevel min-max optimization
- A comparison of solution strategies for biobjective shortest path problems
- A new general-purpose algorithm for mixed-integer bilevel linear programs
- A note on two problems in connexion with graphs
- A projection-based reformulation and decomposition algorithm for global optimization of a class of mixed integer bilevel linear programs
- A study on the computational complexity of the bilevel knapsack problem
- A survey of network interdiction models and algorithms
- A survey on mixed-integer programming techniques in bilevel optimization
- Algorithms for network interdiction and fortification games
- An analytical approach to the protection planning of a rail intermodal terminal network
- An exact algorithm for solving the bilevel facility interdiction and fortification problem
- An exact approach for the bilevel knapsack problem with interdiction constraints and extensions
- An exact solution approach for the interdiction median problem with fortification
- Bilevel knapsack with interdiction constraints
- Bilevel programming and the separation problem
- Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem
- Complexity of the multilevel critical node problem
- Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
- Exact interdiction models and algorithms for disconnecting networks via node deletions
- Improved \(x\)-space algorithm for min-max bilevel problems with an application to misinformation spread in social networks
- Integer programming methods for solving binary interdiction games
- Interdiction Games and Monotonicity, with Application to Knapsack Problems
- Multilevel approaches for the critical node problem
- On integer and bilevel formulations for the \(k\)-vertex cut problem
- On the use of intersection cuts for bilevel optimization
- Optimizing dynamic investment decisions for railway systems protection
- Shortest-path network interdiction
- Survivable network design under optimal and heuristic interdiction scenarios
- The maximum clique interdiction problem
- The multi-terminal maximum-flow network-interdiction problem
- Tri-level mixed-binary linear programming: solution approaches and application in defending critical infrastructure
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)
