We consider mixed integer bilevel linear optimization problems in which the decision variables of the lower-level (follower’s) problem are all binary. We propose a general modeling and solution framework motivated by the practical reality that in a Stackelberg game, the follower does not always solve their optimization problem to optimality. They may instead implement a locally optimal solution with respect to a given upper-level (leader’s) decision. Such scenarios may occur when the follower’s computational capabilities are limited, or when the follower is not completely rational. Our framework relaxes the typical assumption of perfect rationality that underlies the standard modeling framework by defining a hierarchy of increasingly stringent assumptions about the behavior of the follower. Namely, at level k of this hierarchy, it is assumed that the follower produces a k-optimal solution. Associated with this hierarchy is a hierarchy of upper and lower bounds that are in fact valid for the classical case in which complete rationality of the follower is assumed. Two mixed integer linear optimization problem (MILP) formulations are derived for the resulting bilevel optimization problems. We demonstrate how the framework can be applied to develop algorithms for several variants of the bilevel minimum spanning tree problem. Extensive computational results are provided to demonstrate the effectiveness of the proposed MILP formulations and the quality of the bounds produced. The latter are shown to dominate the standard approach based on a single-level relaxation at a reasonable computational cost.
Citation
COR@L Technical Report 20T-012-R2, Lehigh University.