Abstract

Bilevel optimization problems are known to be challenging to solve in practice. In particular, the feasible set of a bilevel problem is, in general, non-convex, even for linear bilevel problems. In this work, we aim to develop a better understanding of the feasible set of linear bilevel problems. Specifically, we develop means by which to identify when a bilevel problem is unbounded or infeasible. We show that extending the well-known high point relaxation with lower-level dual feasibility constraints is relevant to detecting when a bilevel problem is infeasible due to its lower-level problem being unbounded. Moreover, we present a new linear model to detect that a bilevel problem is unbounded when that unboundedness originates from the upper-level variables alone. Furthermore, we derive two sets of sufficient conditions to guarantee bilevel boundedness. Finally, we highlight that constraints that are implied by others are not necessarily redundant for bilevel problems.