An algorithm for the discrete bilevel programming problem

The bilevel programming problem (BLPP) is an example of a two-stage, non-cooperative game in which the first player can influence but not control the actions of the second. This article addresses the linear formulation and presents a new algorithm for solving the zero-one case. The authors begin by converting the leader’s objective function into a parameterized constraint, and then attempt to solve the resultant problem. This produces a candidate solution that is used to find a point in the BLPP feasible region. Incremental improvements are sought, which ultimately lead to a global optimum. An example is presented to highlight the computations and to demonstrate some basic characteristics of the solution. Computational experience indicates that the algorithm is capable of solving problems with up to 50 variables in a reasonable amount of time.