An Algorithm for Solving the General Bilevel Programming Problem

The conflict that naturally arises in a hierarchical system can often be modeled as a multistage optimization problem. This paper considers the sequential uncooperative problem in which two decision makers wish to maximize their own objective functions over a feasible region defined by interactive strategy sets. The resultant problem is known as the bilevel program. Such programs are inherently nonconvex and resistant to standard nonlinear programming solution techniques such as piecewise linearization and convex underestimating envelopes. Alternatively, a grid search algorithm is offered which exhibits the desirable property of monotonicity. The algorithm is based on two sets of necessary conditions previously developed and combined here to provide an operational check for stationarity and local optimality. Potential solutions are obtained from a parameterized master program whose feasible region approximates that of the original problem. As the one-dimensional parameter is varied over the unit interval and the master problem solved, a nondecreasing sequence of lower bounds to the first decision maker’s objective function is produced. If the solution to the original problem is stable under small perturbations, the sequence is shown to converge to the global optimum. A discussion of the computational requirements follows the presentation of the algorithm.