A cutting plane method for linear bilevel programs

In this paper, a cutting plane method is presented for solving the linear bilevel programming problem (BLPP). An optimality criterion for the linear BLPP is derived from two related linear programs constructed by using the complementarity conditions for the second level problem. Two types of cutting planes are developed in order to deal with different situations and to obtain a maximal efficiency. The method makes uses of the special cuts and the implicit vertex enumeration idea to avoid some drawbacks in some existing cutting plane methods. The algorithm can be proved to be finitely convergent.