The Linear-quadratic Bilevel Programming Problem

Recently the authors have developed a Sequential LCP (SLCP) algorithm for the solution of the Linear Bilevel Programming Problem (LBLP). The SLCP algorithm consists of solving a sequence of Linear Complementarity Problems (LCP) by a hybrid enumerative method. In this paper the authors show that the SLCP algorithm can successfully solve the Linear-quadratic Bilevel Programming Problem (LQBLP), if some modifications are introduced in the hybrid enumerative method. The LQBLP was introduced by Bard and Moore, who proposed a Branch-and-Bound method for its solution. Computational experience with the SLCP and Branch-and-Bound methods for small and medium scale LQBLPs shows that the SLCP algorithm is consistently more efficient and the gap increases with the dimension of the LQBLP. As for the LBLP, the SLCP algorithm is shown to be quite efficient at finding a global minimum for the LQBLP, but it is harder to establish that such solution has been found.