There are several global optimization solvers available that handle a wide variety of variables (continuous, integer, mixed-integer) and nonlinear functions, such as BARON [6], MAiNGO [7], and ANTIGONE [8]. While many optimization problems can be handled effectively with these tools, we focus on large problems that rely on decomposition for reasonable solution times. Decomposing optimization problems becomes critical for large-scale instances, as optimization techniques can focus on solving significantly smaller subproblems, ideally leveraging modern high-performance computers (HPC) to solve these subproblems in parallel.
While many well-established decomposition methods are available in the literature (e.g., Dantzig-Wolfe, Bender’s) few approaches have been developed for the decomposition and global optimization of nonconvex problems. Li and Grossmann [3] (L&G) proposed a generalized Bender’s decomposition-based branch and cut algorithm for two-stage stochastic programs with nonconvex constraints, where the authors employ a similar priority-based spatial branch-and-bound approach as C&Z. In a two-stage stochastic program, there are two sets of variables: first-stage variables appear in every subproblem (and are considered complicating) whereas the second-stage variables appear only in their associated subproblem (and are, therefore, non-complicating since they do not couple subproblems). Both L&C and C&Z rely on a spatial branch-and-bound algorithm, branching on the first-stage (complicating) variables; branching on the second-stage (non-complicating) variables is handled implicitly by solving each subproblem to global optimality. The key difference between L&C and C&Z is relaxations; C&Z relies on piecewise linear underestimators, while L&C focuses on combining Bender’s and Lagrangian cuts. It is important to note that both L&C and C&Z suffer from the well-known clustering problem (except for L&C in the case of twice-continuously differentiable problems) [9]; however, given the size of the problems we aim to solve, this approach still holds substantial practical potential, as we have demonstrated through numerous case studies.
SNoGloDe defines the complicating variables of a decomposable block-angular problem as the branching variables within the spatial branch-and-bound tree. Note that we convert the complicating variables into complicating constraints by creating subproblem-specific copies of the complicating variables and imposing equality constraints across all subproblems. We perform spatial branch-and-bound by traversing a tree that repeatedly refines the bounds of continuous and/or integer branching variables to explore the feasible space. At each node, a lower bounding problem is defined by dropping complicating constraints that enforce consensus among the complicating variables in each subproblem; in this way, all subproblems can be solved in parallel. Note that we do not require linear or even convex relaxations; given the state of global optimization solvers, many small nonconvex optimization problems can be solved in a reasonable time frame. SNoGloDe provides a custom plug-in for users to refine their relaxation further. A candidate (i.e., feasible) solution can be determined at the same node to find an upper bound. C&Z proposed solving the Extensive Form (EF) of the problem (where the previously dropped complicating constraints are reinstated) to a locally optimal solution, using the solution for the complicating variables as the candidate. SNoGloDe has this functionality and an averaging capability; we also provide a plug-in space for users to define custom candidate generators.
The spatial branch-and-bound tree size is reduced by pruning nodes based on infeasibility (if the lower bounding problem is infeasible) or by bound (if the node’s lower bound is greater than the best upper bound). Non-pruned nodes spawn children with new bounds, and a new node is selected; the search continues until the optimality gap reaches a sufficient epsilon-tolerance. To reduce the search space, we use the Pyomo [2] implementations of Optimization Based Bounds Tightening (OBBT) and Feasibility Based Bounds Tightening (FBBT) on each node before proceeding to solve the lower and upper bounding problems. Additionally, selecting which variable to branch on when spawning children and (in the case of a continuous variable) where to split the domain of the variable can have a significant impact on the algorithm convergence; SNoGloDe provides several built-in options but also has custom plug-ins for branching variable selection and continuous variable domain splitting choice.
The algorithmic framework provided by C&Z was fundamental for the structure behind SNoGloDe. Building on their foundational work, SNoGloDe extends beyond nonlinear two-stage stochastic programs to general block angular problems that can be mixed integer, nonlinear, linear, or a combination. We have demonstrated the usefulness of this approach outside of the nonlinear setting, as shown in Bynum et al. [4], to solve a large-scale MILP. We have also demonstrated extrapolation outside of two-stage stochastic programming, employing a temporal decomposition of a produced water network [3]. SNoGloDe is intended for use across a wide variety of problems. Coupled with its plug-in framework that allows for the elements of the spatial branch-and-bound tree to be customized to problem-specific instances, we plan to continue solving a diverse set of large-scale optimization problems. Future work involves integrating Lagrangian relaxation and Lagrange multiplier updates to the work C&Z proposed, as a means to improve the lower bounding convergence.
Disclaimer
Sandia National Laboratories is a multimission laboratory managed and operated by National Technology & Engineering Solutions of Sandia, LLC, a wholly owned subsidiary of Honeywell International Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA0003525.
References