ALGORITHMS FOR NONLINEAR BILEVEL MATHEMATICAL PROGRAMS

The bilevel programming problem (BLPP) is a model of a leader-follower game in which play is sequential and cooperation is not permitted. In the first part of the paper, some basic properties of the general model are developed and a conjecture relevant to solution procedures is presented. Next, two algorithms are presented for solving various versions of the game when certain convexity conditions hold. One algorithm relies upon a hybrid branch and bound scheme, and it does not guarantee global optimality. Another is based upon objective function cuts and, barring numerical stability problems with the optimize, is guaranteed to converge to an epsilon-optimal solution. Finally, performance of the two algorithms is examined using randomly generated test problems. The computational performance of the branch and bound algorithm is explored, and the cutting plane algorithm is used to determine whether or not the branch and bound algorithm is uncovering global optima.