Bi-level problems are optimisation problems in which some of the decision variables must optimise a subordinate (lower-level) problem. In general, the lower-level problem can possess multiple optimal solutions. One therefore distinguishes between optimistic formulations, which assume that the most favourable lower-level solution is implemented, and pessimistic formulations, in which the most adverse lower-level solution is adopted. In this paper we study the pessimistic bi-level problem without making any convexity assumptions. We analyse the structural properties of this problem, and we develop a convergent sequence of solvable approximations. We then propose an iterative solution scheme, and we present a computational study that investigates the numerical behaviour of the algorithm.
Working Paper, Imperial College London and Massachusetts Institute of Technology, January 2012