A Branch and Bound Algorithm for the Bilevel Programming Problem

TLDR

Bilevel programming is a static Stackelberg game in which two players sequentially and uncooperatively maximize their own objective functions. The paper proposes an algorithm for solving the linear and quadratic bilevel programming problem. The authors reformulate the problem as a standard mathematical program using the follower’s Kuhn–Tucker conditions and apply a branch‑and‑bound scheme based on Fortuny‑Amat and McCarl to enforce complementary slackness. An illustrative example demonstrates the method, with results reported for instances up to 60 leader variables, 40 follower variables, and 40 constraints, highlighting detailed implementation steps and extensive testing.

Abstract

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 Fortuny-Amat and McCarl 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. The main contributions of the paper are in the step-by-step details of the implementation, and in the scope of the testing.