(119b) Improving the Efficiency of Branch-and-Bound for Global Dynamic Optimization

This talk will present a new improved spatial branch-and-bound (B&B) method for solving dynamic optimization (DO) problems to global optimality. Global dynamic optimization (GDO) is crucial in many applications, ranging from optimal control of batch reactions to motion planning with rigorous safety guarantees. Spatial B&B can currently only solve GDO problems with around 5 states and 10 decision variables in a few hours on a personal computer [5]. This falls far short of the target of solving GDO problems at the industrial scale, which often contain hundreds of states and decision variables. Furthermore, solving DO problems to local optimality is also not a viable approach, since real DO problems often contain hundreds of local suboptimal solutions, many of which can lead to significant economic loss and performance degradation [1].

For standard nonlinear programming (NLP) problems, the efficiency of B&B global optimization algorithms depends largely on the tightness (or accuracy) of lower bounds furnished by convex relaxations. Thus, a wide variety of techniques have been developed to construct tighter convex relaxations. Among these, many of the most effective techniques involve the addition of cuts, which are additional constraints that are redundant in the original problem, but not in the relaxation. The use of cuts often results in major speed-ups and the ability to solve much larger NLPs [4,6]. However, there are no methods in the existing literature for deriving and making use of cuts within B&B algorithms for GDO. GDO algorithms also rely on convex relaxations and often suffer from relaxations that are too weak. In particular, such algorithms rely on so-called state relaxations, which are convex and concave relaxations of the variables that change with time in DO problems. State relaxations tend to weaken over time, and it is the state relaxations at the final time that affect the efficiency of the B&B algorithm. Though many methods exist in literature for computing state relaxations, none of them adequately address this issue of growing state relaxation weakness over time.

In the 2022 AIChE meeting, we presented the first method for using cuts to tighten state relaxations, particularly mitigating their growing weakness over time. We first proposed an iterative algorithm that refines pairs of convex and concave relaxations based on linear cuts [3]. We then showed that this iterative algorithm can be embedded within the right-hand side expressions of ordinary differential equations (ODEs) describing the state relaxations. Specifically, we embedded this iterative algorithm within the ODEs from a state-of-the-art method, known as relaxation preserving dynamics (RPD) [2], for computing state relaxations. By numerically integrating these resulting ODEs, state relaxations are refined using these linear cuts at each point in time prior to being propagated to the next time point. We observed significantly tighter state relaxations at final time, as desired, for multiple example problems compared to using RPD without linear cuts. However, we did not yet embed this improved relaxation technique into a complete B&B code and test its performance for solving GDO problems.

In this talk, we apply this method of state relaxation tightening with linear cuts to the spatial B&B method for solving GDO problems as a whole and demonstrate the improvement in computational time on a test set of challenging problems. We also present detailed comparisons with existing state-of-the-art solvers for GDO. By being capable of solving, within a more reasonable time, larger DO problems to global optimality than previously, this improved spatial B&B method is a major step towards realizing the goal of solving GDO problems closer to the practical scale.

References

[1] Adam B. Singer, James W. Taylor, Paul I. Barton, and William H. Green. Global dynamic optimization for parameter estimation in chemical kinetics. The Journal of Physical Chemistry A, 110(3):971–976, 2006

[2] AIChE: An Improved Implementation of the RPD Method for Computing Convex Relaxations for Global Dynamic Optimization (2021)

[3] AIChE: Improving the Tightness of State Relaxations for Global Dynamic Optimization through Refinement with Linear Cuts (2022)

[4] Nikolaos V. Sahinidis and Mohit Tawarmalani. Accelerating branch-and-bound through a modeling language construct for relaxation-specific constraints. Journal of Global Optimization, 32:259–280, June 2005.

[5] Spencer D. Schaber. Tools for Dynamic Model Development. PhD thesis, Massachusetts Institute of Technology, June 2014.

[6] Xiaowei Bao, Aida Khajavirad, Nikolaos V. Sahinidis, and Mohit Tawarmalani. Global optimization of nonconvex problems with multilinear intermediates. Mathematical Programming Computation, 7:1–37, May 2015.