Generalizing single-level relaxations for bilevel linear programs

We consider a broad class of bilevel linear programs in which the follower’s decisions are all continuous, while the leader’s decisions may include integrality restrictions. Solving such problems to optimality is known to be NP-hard. A classical approach in bilevel optimization for constructing lower and upper bounds is based on a single-level relaxation, in which the follower’s objective function is dropped. Equivalently, the leader is assumed to “fully control” all of the follower’s variables, which reduces the original bilevel program to a single-level optimization problem. We propose a generalization of this approach in which the leader controls only a subset of the follower’s variables. This simple generalization yields a hierarchy of lower and upper bounds, with an underlying trade-off between the quality of the bounds and the computational difficulty of obtaining them. Finally, we provide some preliminary computational observations.

Article

Download

View PDF