(398g) A Deterministic Global Optimization Algorithm, Branch-and-Sandwich, for Optimistic Bi-Level Programming Problems: Implementation and Computational Results

We describe an implementation of the Branch-and-Sandwich algorithm, introduced in (Kleniati and Adjiman, J. Global Optim., 2012), which can be used to solve optimistic bi-level programming problems, where the inner problem is nonconvex but satisfies a regularity condition, and the functions involved are twice continuously differentiable. The main components of the algorithm are (i) the partition of both the inner and the outer spaces without distinction, but at the same time the consideration of all inner (successively refined) subdomains, where global optima may lie, for successively refined outer subdomains; (ii) the generation of guaranteed upper and lower bounds on the inner optimal value function and on the outer objective value for a given region - the proposed bounding problems are nonconvex but do not grow in size with the number of iterations and are always obtained from the corresponding problems of the parent node; (iii) the appropriate tree management with auxiliary lists of nodes as well as inner and outer fathoming rules. The theoretical convergence properties have also been investigated in the aforementioned work and the Branch-and-Sandwich algorithm was proved to be epsilon-convergent, i.e. at termination an epsilon-optimal solution of the bi-level problem is computed. This result followed from exhaustiveness and the general theory concerning the convergence of branch-and-bounds methods developed in (Horst and Tuy, Springer-Verlag, Third ed., 1996). The Branch-and-Sandwich algorithm was tested on 33 small problems with promising numerical results. The full implementation of the algorithm and computational experience are the focus of the present work. Practical considerations, algorithmic options and performance on larger problems are explored. In particular, the efficiency of the algorithm is strongly dependent on the progress of the outer lower bound on the global optimal value of the bi-level problem, which in turn may often be dependent on the progress of the inner upper bound. In addition, what choices we make with respect to how the global optimization subproblems are tackled, e.g. via convexification versus solving them directly to global optimality, may affect the performance of the algorithm. The C++ implementation of the algorithm is a customization of the branch-and-bound platform provided by the MINOTAUR open-source toolkit (Leyffer, Mahajan, Munson, Linderoth and Luedtke).