Groupe d’études et de recherche en analyse des décisions

G-95-33

An Exact Algorithm for Convex Bilevel Programming

, et

We propose a new exact algorithm for the convex-quadratic bilevel programming problem, i.e, for problems with convex objective function and convex constraints at the first level, and quadratic convex objective function with linear constraints at the second level. It generalizes a previous algorithm of Hansen, Jaumard and Savard (1992) for the linear bilevel programming problem. Dual cuts are iteratively introduced in the primal relaxation problem to improve on the subproblem fathoming. New optimality conditions are given, expressed in terms of tightness of the constraints of the second level, valid for the convex bilevel problem (i.e., with convex programs at each level). They can be used to fathom or simplify subproblems and to define separations. A computational comparison with Bard and Moore's (1990) algorithm is reported for linear-quadratic and convex-quadratic problems with up to 50 constraints, 60 variables controlled by the leader and 40 variables controlled by the follower.

, 23 pages