Generating quadratic bilevel programming test problems

Abstract

This paper describes a technique for generating sparse or dense quadratic bilevel programming problems with a selectable number of known global and local solutions. The technique described here does not require the solution of any subproblems. In addition, since most techniques for solving these problems begin by solving the corresponding relaxed quadratic program, the global solutions are constructed to be different than the global solution of this relaxed problem in a selectable number of upper- and lower-level variables. Finally, the problems that are generated satisfy the requirements imposed by all of the solution techniques known to the authors.