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

Abstract We present MUSE-BB, a branch-and-bound (B&amp;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&amp;B in an outer B&amp;B on the first-stage variables, we branch on all variables within a single B&amp;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&amp;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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ε</mml:mi> <mml:mi>f</mml:mi> </mml:msub> </mml:math> -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.