  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.

Optimization and Control;Discrete Mathematics