(468e) GPU-Enhanced Deterministic Global Optimization

Challenging problems for deterministic global optimization often require significant branching before relaxations are sufficiently tight to begin fathoming. The high computational expense of B&B for such problems comes from the necessity to process this large number of nodes. In other application spaces with computationally expensive but highly repetitive tasks, such as in machine learning model training [1] and data analysis [2], software acceleration using graphics processing unit (GPU) hardware has emerged as the dominant strategy. However, in deterministic global optimization, all existing solvers, with the exception of the solver created by the present authors, continue to rely exclusively on CPU computation. Although improvements to bounds tightening techniques [3], tighter relaxations [4, 5], and other techniques [6, 7] have been---and continue to be---highly successful at reducing overall computation times, accelerating solve times in general for global optimization problems using GPUs remains a comparatively unexplored path.

To date and to the best of our knowledge, we are the only group to have demonstrated a GPU-accelerated method of solving NLPs to guaranteed global optimality using relaxations of the objective and constraints. We first showed that McCormick relaxations [8, 9] could be efficiently calculated on multiple domains simultaneously using the single-instruction multiple-data (SIMD) architecture of GPUs [10, 11]. Subsequently, we showed that relaxation subgradient calculations could similarly be accelerated on GPUs [12], and at the recent ISMP 2024, we illustrated how these subgradients could be used to create a large number of LPs which, when solved in parallel using a suitably accelerated LP solver, represented a viable path toward a general-purpose GPU-accelerated deterministic global optimizer [13].

The ability to create and solve LPs using subgradients is critical for the lower-bounding procedures of modern, high-performance global optimizers. While subgradient-free methods of obtaining lower bounds exist, such as the method of sampling convex relaxation values [14, 15] that was utilized in our previous work [10, 11], tighter lower bounds---and therefore faster overall convergence---can be achieved by making use of subgradient information. For this reason, all global optimizers that we are aware of compute and utilize relaxation subgradients. In the EAGO solver [16], for example, subtangent hyperplanes from multiple evaluations of the objective and constraints are combined to form a polyhedral outer-approximation of the relaxation, which is then passed to an LP subsolver such as GLPK [17] or Gurobi [18] to obtain a tight lower bound. While the use of GPUs enables our solver to have faster calculation throughput than existing CPU-based solvers, it is critical to integrate a compatible LP solver to be competitive with state-of-the-art commercial tools.

In this talk, we will focus on this crucial, keystone component of our general-purpose GPU-accelerated deterministic global optimizer. Namely, we will discuss the development of a modified PDLP algorithm [19, 20] that is designed for GPU acceleration for the simultaneous solution of thousands of small-scale LPs, as well as our incorporation of this custom solver within the parallel B&B framework established in our previous work [11]. This LP-enhanced framework, built as an extension of the open-source EAGO solver [16], enables a substantial speed-up over traditional CPU-based deterministic global optimization methods without compromises on the lower-bounding technique. With these new developments, we have observed speedups of greater than an order-of-magnitude over the equivalent CPU-based solver in several test cases. We will more broadly demonstrate the effectiveness of this approach by applying it to solve benchmark test set problems, across a range of hardware capabilities, and against commercially available CPU-based optimizers.

[1] Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dan Mane, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viegas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. Tensorflow: Large-scale machine learning on heterogeneous distributed systems, 2016.

[2] Hardik Singh, Raavi Sai Venkat, Sweta Swagatika, and Sanjay Saxena. GPU and CUDA in hard computing approaches: Analytical review. In Lecture Notes in Electrical Engineering, pages 177–196. Springer International Publishing, nov 2019. doi: 10.1007/978-3-030-29407-6 15.

[3] Yi Zhang, Nikolaos V. Sahinidis, Carlos Nohra, and Gang Rong. Optimality-based domain reduction for inequality-constrained NLP and MINLP problems. Journal of Global Optimization, 77(3):425–454, February 2020. ISSN 1573-2916. doi: 10.1007/s10898- 020-00886-z.

[4] Anatoliy Kuznetsov and Nikolaos V. Sahinidis. New bounds and formulations for the deterministic global optimization of Lennard–Jones clusters. Journal of Global Optimization, March 2025. ISSN 1573-2916. doi: 10.1007/s10898-025-01476-7.

[5] Matthew E. Wilhelm, Chenyu Wang, and Matthew D. Stuber. Convex and concave envelopes of artificial neural network activation functions for deterministic global optimization. Journal of Global Optimization, aug 2022. doi: 10.1007/s10898-022-01228-x.

[6] David R. Morrison, Sheldon H. Jacobson, Jason J. Sauppe, and Edward C. Sewell. Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning. Discrete Optimization, 19:79–102, February 2016. ISSN 1572-5286. doi: 10.1016/j.disopt.2016.01.005.

[7] Timo Berthold. Heuristic algorithms in global MINLP solvers. PhD thesis, Technischen Universität Berlin, 2014.

[8] Alexander Mitsos, Benoît Chachuat, and Paul I. Barton. McCormick-based relaxations of algorithms. SIAM Journal on Optimization, 20(2):573–601, jan 2009. doi: 10.1137/080717341.

[9] Joseph K. Scott, Matthew D. Stuber, and Paul I. Barton. Generalized McCormick relaxations. Journal of Global Optimization, 51(4):569–606, feb 2011. doi: 10.1007/s10898-011-9664-7.

[10] Robert X. Gottlieb and Matthew D. Stuber. Global dynamic optimization using hardware-accelerated programming. In AIChE Annual Meeting 2022, Phoenix, AZ, November 2022. AIChE.

[11] Robert X. Gottlieb, Pengfei Xu, and Matthew D. Stuber. Automatic source code generation for deterministic global optimization with parallel architectures. Optimization Methods and Software, pages 1–39, 2024. doi: https://doi.org/10.1080/10556788.2024.2396297.

[12] Robert X. Gottlieb, Pengfei Xu, and Matthew D. Stuber. Automatic source code generation of complicated models for deterministic global optimization with parallel architectures. In FOCAPO-CPC 2023, San Antonio, TX, January 2023. FOCAPO-CPC.

[13] Robert X. Gottlieb and Matthew D. Stuber. GPU-accelerated deterministic global optimization. In ISMP 2024, Palais des congrès de Montréal, Montréal, Canada, July 2024. ISMP.

[14] Felix Bonhoff and Kamil Khan. Evaluating lower bounds in global optimization via cheaper sampling of convex relaxations. In 2023 AIChE Annual Meeting, 2023.

[15] Yingkai Song, Huiyi Cao, Chiral Mehta, and Kamil A. Khan. Bounding convex relaxations of process models from below by tractable black-box sampling. Computers & Chemical Engineering, 153:107413, oct 2021. doi: 10.1016/j.compchemeng.2021.107413.

[16] Matthew E. Wilhelm and Matthew D. Stuber. EAGO.jl: easy advanced global optimization in Julia. Optimization Methods and Software, 37(2):425–450, aug 2022. doi: 10.1080/10556788.2020.1786566.

[17] Andrew Makhorin. GLPK (GNU linear programming kit). http://www.gnu.org/s/glpk/glpk.html, 2008.

[18] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024. URL https://www.gurobi.com.

[19] David Applegate, Mateo Díaz, Oliver Hinder, Haihao Lu, Miles Lubin, Brendan O’Donoghue, and Warren Schudy. Practical large-scale linear programming using primal-dual hybrid gradient. June 2021. doi: 10.48550/ARXIV.2106.04756.

[20] Haihao Lu and Jinwen Yang. cuPDLP.jl: A GPU implementation of restarted primal-dual hybrid gradient for linear programming in Julia. April 2024. doi: 10.48550/ARXIV.2311.12180.