(101d) Unraveling and Exploiting Complex Structures in Optimization Using Algebraic Graphs

Significant advances in parallel and distributed optimization algorithms have been reported in recent years [1,2,3]. Problem-level decomposition algorithms such as Lagrangian [4], Benders [5,6], and Dantzig-Wolfe [7,8] decomposition are now routinely used to tackle large problems. Moreover, linear-algebra decomposition techniques such as Schur complement decomposition [9,10] and block preconditioners [11] are now available within interior point solvers. While algorithmic advances have been significant, the development of modeling abstractions that support such algorithms has remained rather limited [12,13]. For instance, available modeling tools often only capture obvious structures (e.g., time or scenario decomposition) [14,15]; problems of interest, however, often contain complex non-obvious structures (e.g. hierarchical or space-time structures) that are difficult to unravel and exploit.

Graphs provide a flexible modeling paradigm to analyze complex structures of optimization problems and to exploit such structures to perform model processing and visualization tasks [16,17,18]. This talk introduces the notion of an algebraic graph, which is a modeling abstraction of optimization problems that facilitates the scalable implementation, decomposition, and solution of complex problems [19]. In an algebraic graph, optimization models live over nodes containing local variables and constraints and are connected through edges by means of linking (or hyper) constraints which allows for systematic creation of distributed and hierarchical optimization structures. The algebraic graph enables diverse partitioning tasks such as community detection and hypergraph partitioning [20,21], which can be combined with interfaces to employ state-of-the art algorithms and to develop new algorithms that exploit graph properties [22,23].

We demonstrate the advantages of the algebraic graph within the Julia-based framework Plasmo.jl. Here, we show how these capabilities enable the decomposition of large-scale natural gas planning problems [24]. Specifically, we show that our framework reveals non-obvious space-time structures that can be exploited to gain physical insights on the problem and to accelerate computations. The structures are revealed by using a hypergraph partitioning strategy and we show how we can obtain efficient partitions that mitigate load-imbalancing issues. We also show how algebraic graphs facilitate the development of overlapping Schwarz decomposition algorithms. Specifically, we show how to use partitioning, node neighborhood expansion, and node aggregation functions within Schwarz schemes to tackle challenging problems arising in energy networks and model predictive control [25].

[1] Ledet WP, Himmelblau DM. "Decomposition procedures for the solving of large scale systems." Advances in Chemical Engineering. (1970).

[2] Conejo AJ, et al. "Decomposition techniques in mathematical programming." Engineering and science applications. (2006).

[3] Birgin EG, Martinez JM. "Practical Augmented Lagrangian Methods for Constrained Optimization." (2014).

[4] K. Kim and V. M. Zavala. "Algorithmic innovations and software for the dual decomposition method applied to stochastic mixed-integer programs." Mathematical Programming Computation (2018), volume 10, 225–266.

[5] Geoffrion, Arthur M. "Generalized benders decomposition." Journal of optimization theory and applications 10.4 (1972): 237-260.

[6] Sahinidis NV and Grossman IE. "Convergence properties of generalized benders decomposition". Computers and Chemical Engineering. (1991).

[7] Dantzig GB and Wolfe P. "Decomposition Principle for Linear Programs." Operations Research (1960).

[8] Bergner M, et al. "Automatic Dantzig–Wolfe reformulation of mixed integer programs." Mathematical Programming. (2015) 149, 391–424.

[9] Kang J, et al. "An interior-point method for efficient solution of block-structured NLP problems using an implicit Schur-complement decomposition." Computers and Chemical Engineering (2014).

[10] Kourounis D and Schenk O. "Structure-Exploiting Interior Point Methods."

[11] Rodriguez JS, Laird CD and Zavala VM. "Scalable preconditioning of block-structured linear algebra systems using ADMM." Computers and Chemical Engineering. (2020). 133.

[12] Kang J, et al. Nonlinear programming strategies on high-performance computers. In Decision and Control (CDC), IEEE 54th Annual Conference,(2015),pp. 4612–4620.

[13] Daoutidis P, Tang W, and Allman A. "Decomposition of control and optimization problems by network structure: Concepts, methods, and inspirations from biology." AIChE Journal. (2019).

[14] Huchette J, Lubin M, Petra C. Parallel algebraic modeling for stochastic optimization. The International Conference for High Performance Computing, Networking, Storage and Analysis (2014).

[15] Watson JP, Woodruff DL, and Hart WE. "PySP: Modeling and solving stochastic programs in Python." Mathematical Programming Computation. (2012).

[16] Tang W, et al. Optimal decomposition for distributed optimization in nonlinear model predictive control through community detection. Computers & Chemical Engineering, (2017), 111, 43–54.

[17] Allman A, Tang W, and Daoutidis P. "Decode: a community-based algorithm for generating high-quality decompositions of optimization problems." Optimization and Engineering. (2019).

[18] Farina F, et al. "DISROPT : a Python Framework for Distributed Optimization." arXiv preprint arxiv:1911.02410, (2019).

[19] Jalving J, Cao Y and Zavala VM. "Graph-based modeling and simulation of complex systems." Computers & Chemical Engineering. (2019). 125, 134-154.

[20] Fortunato S. "Community detection in graphs." Physics Reports. (2010), 486, 75–174.

[21] Akhremtsev Y, et al. "Engineering a direct k-way hypergraph partitioning algorithm." In 19th Workshop on Algorithm Engineering and Experiments, (2017), pp. 28–42.

[22] Chiang N, Petra CG, and Zavala VM. "Structured nonconvex optimization of large-scale energy systems using PIPS-NLP." In Proc. of the 18th Power Systems Computation Conference (2014).

[23] Sungho S, Anitescu M, and Zavala VM. "Overlapping Schwarz Decomposition for Constrained Quadratic Programs." arXiv preprint arXiv:2003.07502, (2020).

[24] Chiang NY and Zavala VM. "Large-scale optimal control of interconnected natural gas and electrical transmission systems." Applied Energy. (2016). 168, 226–235.

[25] Coffrin C, et al. "Powermodels. jl: An open-source framework for exploring power flow formulations." 2018 Power Systems Computation Conference (PSCC). IEEE, 2018.