Optimization Online


Branch-and-Sandwich: A Deterministic Global Optimization Algorithm for Optimistic Bilevel Programming Problems

Polyxeni-M. Kleniati (polyxeni.kleniati03***at***imperial.ac.uk)
Claire S. Adjiman (c.adjiman***at***imperial.ac.uk)

Abstract: We present a global optimization algorithm, Branch-and-Sandwich, for optimistic bilevel programming problems which satisfy a regularity condition in the inner problem. The functions involved are assumed to be nonconvex and twice continuously differentiable. 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. A novel branching scheme is developed such that classical branch-and-bound is applied to both spaces without violating the hierarchy in the decisions and the requirement for (global) optimality in the inner problem. To achieve this, the well-known features of branch-and-bound algorithms are customized appropriately. For instance, two pairs of lower and upper bounds are computed: one for the outer optimal objective value and the other for the inner value function. The proposed bounding problems do not grow in size during the algorithm and are obtained from the corresponding problems at the parent node. The theoretical properties of the algorithm are investigated and finite $\epsilon$-convergence to a global solution of the bilevel problem is proved. Thirty-four literature problems are tackled successfully.

Keywords: Bilevel Programming, Nonconvex Inner Problem, Branch and Bound

Category 1: Global Optimization (Theory )

Citation: Centre for Process Systems Engineering, Department of Chemical Engineering, Imperial College London, London SW7 2AZ, United Kingdom (2012 article, currently under revision for the Journal of Global Optimization)

Download: [PDF]

Entry Submitted: 11/21/2012
Entry Accepted: 11/21/2012
Entry Last Modified: 02/06/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society