Mixed-integer bilevel representability (Q2220657)

The authors study mixed integer bilevel linear (MIBL) programs. In particular, they show that the sets defined by continuous bilevel constraints, linear complementarity constraints and polyhedral reverse convex constraints are all equivalent and they are all equal to the family of finite unions of polyhedra as well as every finite union of polyhedra can be described in one of those three ways -- another result of the paper is that if the integer variables are present only in the upper level of a MIBL program, then its feasible region is equivalent to a finite union of sets defined by mixed integer linear (MIL) programs. The last main result of the paper is that the family of finite unions of sets defined by MIL programs is an algebra of sets. This allows to prove that using integer variables also in the lower level of MIBL does not bring any additional modelling power, up to topological closures.