Branch-and-Sandwich: a deterministic global optimization algorithm for optimistic bilevel programming problems. Part II: Convergence analysis and numerical results

In the first part of this work, we presented a global optimization algorithm, Branch-and-Sandwich, for optimistic bilevel programming problems that satisfy a regularity condition in the inner problem (Kleniati and Adjiman in J Glob Optim, <CitationRef CitationID="CR16">2014</CitationRef>). The proposed approach can be interpreted as the exploration of two solution spaces (corresponding to the inner and the outer problems) using a single branch-and-bound tree, where two pairs of lower and upper bounds are computed: one for the outer optimal objective value and the other for the inner value function. In the present paper, the theoretical properties of the proposed algorithm are investigated and finite <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$\varepsilon $$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mi mathvariant="italic">ε</mi> </math> </EquationSource> </InlineEquation>-convergence to a global solution of the bilevel problem is proved. Thirty-four problems from the literature are tackled successfully. Copyright The Author(s) 2014