(40d) Parapint: Scalable Parallel Solution of Structured Nonlinear Programs

We present Parapint (https://github.com/parapint/parapint), an open-source Python package for efficient, scalable, parallel solution of structured nonlinear programs (NLPs). Parapint builds on Pyomo [1], utilizing PyNumero’s [2] interfaces to the AMPL Solver Library (ASL) [3] for automatic differentiation (AD) and the HSL linear solver MA27 [4] for solution of symmetric indefinite linear systems. Additionally, Parapint exploits problem structure for parallel computation on distributed memory machines with PyNumero’s MPI-based matrices and vectors. Parapint’s design expedites algorithm development by separating the software into three primary modules. First, Parapint contains an interior point algorithm which is written to be independent of both problem structure and the linear solver being used. Second, Parapint contains problem interfaces for building structured KKT systems. Currently, Parapint has problem interfaces for both dynamic optimization problems and stochastic optimization problems, both of which work directly with Pyomo models. Finally, Parapint contains a module for parallel solution of structured linear systems. The problem interfaces build KKT systems with structures (using PyNumero’s MPIBlockMatrix) that can be directly exploited by the linear solvers. For example, block-bordered-diagonal systems are built for solution with Schur-Complement decomposition [5]. This design enables use of a common interior point algorithm to test multiple strategies for solving the KKT system. Currently, Parapint contains both serial and parallel implementations of Schur-Complement decomposition. The parallel version exploits any sparsity in the Schur-Complement to minimize communication overhead, which is critical for dynamic optimization problems [6]. Our numerical results on a stochastic quadratic program (QP) demonstrate nearly perfect scaling to over 1,000 cores. Moreover, on a 2-dimensional partial differential equation (PDE)-constrained optimal control problem, we obtain over 360 times speedup (on 1024 cores) compared to the full-space, serial algorithm. Our results demonstrate that Parapint is a high-level framework for efficient, scalable, parallel solution of NLPs.

Works Cited

1. [1] M. Bynum, G. Hackebeil, W. Hart, C. Laird, B. Nicholson, J. Siirola, J.-P. Watson and D. Woodruff, Pyomo - Optimization Modeling in Python, vol. 67, Berlin: Springer, 2021.

2. [2] J. S. Rodriguez, C. Laird and V. Zavala, "Scalable preconditioning of block-structured linear algebra systems using ADMM," Computers and Chemical Engineering, vol. 133, p. 106478, 2020.

3. [3] D. Gay, "The AMPL modeling language: An aid to formulating and solving optimization problems," in Numerical Analysis and Optimization, 2015.

4. [4] I. Duff and J. Reid, "The multifrontal solution of indefinite sparse symmetric linear equations," ACM Transactions on Mathematical Software, vol. 9, no. 3, pp. 302-325, 1983.