MUSE-BB: a decomposition algorithm for nonconvex two-stage problems using strong multisection branching

Journal of Global Optimization, vol. 92, pp. 837–888

Abstract

Abstract We present MUSE-BB, a branch-and-bound (B&B) based decomposition algorithm for the deterministic global solution of nonconvex two-stage stochastic programming problems. In contrast to three recent decomposition algorithms, which solve this type of problem in a projected form by nesting an inner B&B in an outer B&B on the first-stage variables, we branch on all variables within a single B&B tree. This results in a higher convergence order of the lower bounding scheme, avoids repeated consideration of subdomains, inherent to the nesting of B&B searches, and enables the use of cheaper subproblems. In particular, when branching on second-stage variables, we employ a multisection variant of strong-branching, in which we simultaneously consider one candidate variable from each scenario for branching. By our decomposable lower bounding scheme, the resulting subproblems are independent and can be solved in parallel. We then use strong-branching scores to filter less promising candidate variables and only generate child nodes corresponding to a multisection involving the remaining variables by combining the appropriate subproblem results. We prove finite $$\varepsilon _f$$ ε f -convergence, and demonstrate that the lower-bounding scheme of MUSE-BB has at least first-order convergence under the mild assumption of Lipschitz continuous functions and relaxations. MUSE-BB is implemented and made available open source, as an extension of our deterministic global solver for mixed-integer nonlinear programs, MAiNGO, with OpenMP-parallelization of the decomposable subroutines. Numerical results show that MUSE-BB requires less CPU time than solving the deterministic equivalent using the standard version of MAiNGO; moreover, the parallelized decomposition allows for further reduction in wall time.

Authors 4

1. Marco Langiu corresponding Aachen Process Systems Engineering (AVT.SVT)

   Forschungszentrum Jülich · RWTH Aachen University

   Affiliation as printed

   Institute of Climate and Energy Systems, Energy Systems Engineering (ICE-1), Forschungszentrum Jülich GmbH, Jülich, Germany

   Process Systems Engineering (AVT.SVT), RWTH Aachen University, Aachen, Germany

2. Manuel Dahmen corresponding

   Forschungszentrum Jülich

   Affiliation as printed

   Institute of Climate and Energy Systems, Energy Systems Engineering (ICE-1), Forschungszentrum Jülich GmbH, Jülich, Germany

3. Dominik Bongartz corresponding

   KU Leuven

   Affiliation as printed

   Department of Chemical Engineering, KU Leuven, Leuven, Belgium

4. Alexander Mitsos corresponding Aachen Process Systems Engineering (AVT.SVT)

   Forschungszentrum Jülich · Jülich Aachen Research Alliance · RWTH Aachen University

   Affiliation as printed

   Institute of Climate and Energy Systems, Energy Systems Engineering (ICE-1), Forschungszentrum Jülich GmbH, Jülich, Germany

   JARA-ENERGY, Jülich, Germany

   Process Systems Engineering (AVT.SVT), RWTH Aachen University, Aachen, Germany