Groupe d’études et de recherche en analyse des décisions

G-2019-49

A Progressive approximation approach for the exact solution of sparse large-scale binary interdiction games

et

We present a progressive approximation algorithm for the exact solution of several classes of interdiction games in which two non-cooperative players (namely an attacker and a follower) interact sequentially. The follower must solve an optimization problem that has been previously perturbed by means of a series of attacking actions led by the attacker. These attacking actions aim at augmenting the cost of the decision variables of the follower's optimization problem. The objective, from the attacker's viewpoint, is that of choosing an attacking strategy that reduces as much as possible the quality of the optimal solution attainable by the follower. The progressive approximation mechanism consists in the iterative solution of a relaxed interdiction problem -in which the follower actions are restricted to a subset of the whole solution space-, and of a pricing subproblem invoked with the objective of proving the optimality of the attacking strategy. This scheme is especially useful when the optimal solutions to the follower's subproblem intersect with the decision space of the attacker only in a small number of decision variables. Under this assumption, the progressive approximation method can scale and solve interdiction games otherwise untractable for classical methods. We illustrate the efficiency of this framework on shortest path, 0-1 knapsack and facility location interdiction games.

, 49 pages