(169d) Design, Implementation, and Evaluation of the Branch-and-Sandwich Algorithm for Nonlinear Nonconvex Bilevel Problems

Optimization has become the essential tool in process systems engineering. Many of the optimization problems relevant to chemical engineering are bilevel problems in nature [1, 2] and can thus be framed as two-person, hierarchical optimization problems having a nested inner optimization problem withing the constraints of the outer optimization problem. Examples of such problems are optimization problems in design, parameters estimation in thermodynamic models, simultaneous optimization and heat integration of chemical processes, various competitive marketing strategies.

Special cases of bilevel problems, such as problems of linear (quadratic) – linear (quadratic) type, have been studied extensively and many algorithms have been proposed in the literature [2]. However, the general nonconvex form is a very challenging problem. In [3, 4], a new deterministic global optimization algorithm, named Branch-and-Sandwich (B&S), was introduced for bilevel problems with nonconvexities in both the inner and outer problems, and applied to 34 small benchmark problems.

In current work, we discuss the design (how to choose between different approaches), C++ implementation and algorithmic extensions of the B&S algorithm within the open-source MINOTAUR framework [5]. The B&S algorithm is extended to include heuristics for branching and node selection, as well as alternative management of nodes. The computational performance of the Branch-and-Sandwich algorithm is analyzed for different algorithmic variants by solving the extended set of bilevel benchmark problems and showing its applicability to engineering problems.

1. Biegler, L.T., Grossmann, I.E.: Retrospective on optimization. Comput. Chem. Eng. 28, 1169–1192 (2004).
2. Floudas, C.A., Gounaris, C.E. A review of recent advances in global optimization. J Glob Optim, 45, 3–28 (2009)
3. Kleniati, P.-M., Adjiman, C.S.: Branch-and-Sandwich: a deterministic global optimization algorithm for optimistic bilevel programming problems. Part I: Theoretical development. J Glob Optim, 60(3), 425–458 (2014).
4. Kleniati, P.-M., Adjiman, C.S.: Branch-and-Sandwich: a deterministic global optimization algorithm for optimistic bilevel programming problems. Part II: Convergence analysis and numerical results. J Glob Optim, 60(3), 459–481  (2014).
5. Mahajan, A., Leyffer, S., Munson, T., Linderoth, J., Luedtke, J.: MINOTAUR: Toolkit for Mixed Integer Nonlinear Optimization Problems, http://wiki.mcs.anl.gov/minotaur/index.php/Main_Page.