Bilevel programming deals with models whose constraints embed an auxiliary optimization problem. They are closely related to Stackelberg games in which one agent, the leader, must commit to a strategy that can be observed by the other agent, the follower, before he/she commits to a strategy of his/her own. The problem in such games consists thus in finding a payoff-maximizing mixed strategy for the leader, which corresponds to a bilevel problem with bilinear objectives.
In a Stackelberg Security Game, defender’s security resources must be allocated to protect a subset of targets leading to an exponential number of pure strategies for the defender. Similarly, if the defender is protecting a network by selecting paths, tours or walks, if the security resources are heterogeneous, or if there are multiple types of followers, the corresponding Stackelberg Security Game becomes too large to solve for real applications.
Bilevel problems also arise in logistics. Even if complex problems combining product allocation and transportation issues have been tackled most addressed problems involved location decisions for which Stackelberg equilibria are particularly relevant. Indeed, facility locations are determined at the upper level while the lower level problem consists in allocating customers to the facilities. Among facility location problems, competitive location problems involve two competitive companies (the leader and the follower) which have to locate their facilities in order to maximize their market shares. Bilevel models are well suited for such problems since they capture the interaction between both firms.
The first scientific goal consists in developing algorithms for solving real size Stackelberg security problems. The second one is to attack more realistic variants of Stackelberg security games. The third one is to propose new bilevel programming models and solutions methods for competitive facility location problems.
