In bilevel optimization there are two decision makers, commonly denoted as the leader and the follower. Decisions are made in a hierarchical manner: the leader makes the first move, and then the follower reacts optimally to the leader’s action. It is assumed that the leader can anticipate the decisions of the follower, hence the leader’s optimization task is a nested optimization problem that takes into consideration the follower’s response.
In this talk we focus on branch-and-cut algorithms for dealing with mixed-integer bilevel linear programs (MIBLPs). We focus on a subfamily of MIBLPs in which the leader and the follower share a set of items, and the leader can select some of the items to inhibit their usage by the follower. Interdiction Problems, Blocker Problems, and Critical Node/Edge Detection Problems are some examples of optimization problems that satisfy these conditions. We show how modeling of these problems as two-player Stackelberg games leads to integer programming formulations in the natural space of the variables. We also demonstrate how solving these problems using branch-and-cut algorithms often outperforms state-of-the-art methods from literature.
LJUBIC, I. (2021). [Plenary Speaker] Mixed Integer Bilevel Optimization. Dans: SIAM Conference on Optimization (OP21). Virtual.