A branch and bound algorithm for the bilevel programming problem. (English) Zbl 0702.65060

From authors’ summary: The bilevel programming problem is a static Stackelberg game in which two players try to maximize their individual objective functions. Play is sequential and uncooperative in nature. This paper presents an algorithm for solving the linear/quadratic case.
In order to make the problem more manageable, it is reformulated as a standard mathematical program by exploiting the follower’s Kuhn-Tucker conditions. A branch and bound scheme suggested by J. Fortuny-Amat and B. McCarl [J. Oper. Res. Soc. 32, 783-792 (1981; Zbl 0459.90067)] is used to enforce the underlying complementary slackness conditions. An example is presented to illustrate the computations, and results are reported for a wide range of problems containing up to 60 leader variables, 40 follower variables, and 40 constraints.


65K05 Numerical mathematical programming methods
90C30 Nonlinear programming


Zbl 0459.90067
Full Text: DOI