2017 Annual Meeting

(300a) Basbl: Branch-and-Sandwich Bilevel Solver. Implementation and Computational Study Using Basblib Test Set

Authors

Adjiman, C. S. - Presenter, Imperial College London
Paulavicius, R., Imperial College London, Center for Process Systems Engineering
Mathematical programming and optimization are key activities in process systems engineering, with applications in synthesis, control, design, operations, and planning [1]. Many chemical engineering problems are bilevel optimization problems [1, 2], that is, hierarchical problems with one constraint in the main (outer) optimization problem that is an optimization problem. Examples of bilevel optimization problems are design or parameter estimation problems in which phase equilibrium must be satisfied as a constraints, or problems in which the optimum economic design is sought while minimizing energy consumption. The numerous applications of bilevel programming problems provide a strong incentive for developing efficient solvers for this large class of problems.

In this talk, we discuss BASBL, an implementation of the deterministic global optimization algorithm Branch-and-Sandwich for mixed-integer nonconvex/nonlinear bilevel problems, within the open-source MINOTAUR framework [7]. The solver stems from the original Branch-and-Sandwich algorithm [3, 4] and modifications proposed in our recent works [5, 6]. We also introduce BASBLib, an extensive online library of bilevel benchmark problems collected from the literature. The library is designed to enable contributions from the bilevel optimization community. We use the problems from BASBLib, including problems derived from practical applications, to study the performance of BASBL using different algorithmic options, including a variety of bounding schemes, branching, and node selection strategies.

References

  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. Paulavičius, R. and Adjiman, C.S.: BASBL: Branch-And-Sandwich BiLevel solver. I. Algorithmic improvements and extensions, (2017). Submitted.
  6. Paulavičius, R., Kleniati, P.-M., and Adjiman, C.S. BASBL: Branch-And-Sandwich BiLevel solver. II. Implementation and computational study with the BASBLib test set, (2017). Submitted.
  7. 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.