Anticipating the strategies of potential attackers is crucial for protecting critical infrastructure. We can
represent the challenge of the defenders of such infrastructure as a Stackelberg security game. The defender
must decide how to allocate limited resources to protect specific targets, aiming to maximize their expected
utility (such as minimizing the extent of damage) and considering that attackers will respond in a way that
is most advantageous to them.
We consider two different cases according to whether the defender’s set of mixed strategies can be described with a perfect formulation or not. For both cases, we present exact algorithms to determine the optimal mixed strategies of the defender and validate them through computational experiments.
In particular, we solve a Stackelberg security game that aims to protect targets with a defined budget, i.e. the defender pure strategies must satisfy a knapsack constraint. This game is solved with a branch and price approach.

We consider a multi-commodity traffic network in which a toll-setting authority aims to maximize revenues by imposing tolls on certain arcs of the network. Users of the traffic network act in the sense of Wardrop's user equilibrium so that their individual travel costs are minimized. The problem can be seen as a single-leader multi-follower problem with the toll-setting authority acting as the leader and the network users acting as the followers. We model this setting as a mathematical problem with equilibrium constraints (MPEC), for which we present a single-level mixed-integer nonlinear reformulation. Moreover, we consider the setting in which the network users face uncertainties regarding their travel costs, which we address using a Gamma-robust approach. Our preliminary numerical results illustrate the impact of addressing uncertainties in comparison to nominal solutions.

The field of computational mixed-integer linear bilevel optimization made significant advances over the last 15 years. Many new problem classes have been tackled and a significant number of algorithmic techniques have been introduced. Consequently, we can solve new types of or simply larger problems compared to what was possible in the 2000s. However, what was missing up to now, was a well-curated and publicly available test-set of instances that the community can use to develop, test, and compare novel methods. In this talk, we present the Bilevel Optimization Benchmark Instance Library (BOBILib), which aims for filling the above mentioned gap. BOBILib contains over 2000 instances ranging from general mixed-integer linear bilevel problems to specific interdiction problems. In this talk, we will discuss the structure of the library, the type of instances involved, and the data format in which the problems are given.

Mixed integer bilevel linear optimization problems aim to determine the optimal strategy of the leader in a two-player game, while considering that a follower will also react optimally in response. To adapt the well-known branch-and-cut framework widely used for solving mixed integer linear optimization problem (MILP) to the bilevel setting, it requires an oracle for checking whether the response obtained by solving a relaxation is optimal to follower's problem, given a strategy for the leader. Typically, this is accomplished by solving follower's problem (which is an MILP) to optimality. In this work, we propose a closely related alternative, relying instead on an oracle for determining the existence of an improving feasible direction. The advantage of such an oracle is that it unifies the feasibility check with generation of strong valid inequalities in a way that we conjecture will lead to improvements in empirical performance. Preliminary numerical results are discussed using a modified version of the open source solver MiBS.