New bounding schemes and algorithmic options for the Branch-and-Sandwich algorithm

Abstract We consider the global solution of bilevel programs involving nonconvex functions. Deterministic global optimization algorithms for the solution of this challenging class of optimization problems have started to emerge over the last few years. We present new schemes to generate valid bounds on the solution of nonconvex inner and outer problems and examine new strategies for branching and node selection. We integrate these within the Branch-and-Sandwich algorithm (Kleniati and Adjiman in J Glob Opt 60:425–458, 2014), which is based on a branch-and-bound framework and enables the solution of a wide range of problems, including those with nonconvex inequalities and equalities in the inner problem. The impact of the proposed modifications is demonstrated on an illustrative example and 10 nonconvex bilevel test problems from the literature. It is found that the performance of the algorithm is improved for all but one problem (where the CPU time is increased by 2%), with an average reduction in CPU time of 39%. For the two most challenging problems, the CPU time required is decreased by factors of over 3 and 10.