(41f) Decode – Automated Structure-Based Decomposition and Decomposition-Based Solution of Optimization Problems

Large-scale, complex optimization problems are widely present in process systems engineering, for which a decomposition-based algorithm is a natural and common approach to reduce their complexity. In these algorithms, the problem is decomposed into several subproblems with interactions, i.e., the variables and constraints are assigned to different groups, and iterative schemes are used to coordinate their respective solutions [1]. Among these, Benders and Lagrangian decompositions are the most representative and well-established. However, the prerequisite of implementing these algorithms – the allocation of the variables and constraints to subproblems – is less studied and often performed in a problem-specific way.

Recently, a systematic method of decomposing optimization problems based on detecting the community structures in the corresponding network representations [2] has been proposed, with a software implementation called DeCODe (Detection of Communities for Optimization Decomposition) [3]. In this talk, we demonstrate improvements of DeCODe in the following three aspects.

First, we adopt the Python language (v. 3.6.5) for coding the decomposition and make use of its available packages, including NetworkX (v.2.2) for network construction and manipulations and Pyomo (v.5.6.1) for mathematical optimization, thus allowing a more automated solution procedure compared to our previous version in MATLAB. For example, while the earlier software only addressed the decomposition of variables and constraints and required manual construction of resulting subproblems, here we automatically generate the subproblems within Pyomo after decomposition by removing irrelevant variables and constraints and redefining the objective functions.

Second, in addition to communities, we consider core-periphery structures as desirable for solving optimization problems with a Benders decomposition algorithm. Core-periphery structures in networks refer to the partition of the nodes into two classes of different nature, namely the core and the periphery, such that the interactions involving core nodes are significantly stronger (denser) than the interactions between peripheral nodes. Algorithms of core-periphery structure detection have been an important field within network science in recent years (see e.g., [5]), and we use these efficient algorithms for the automatic decomposition of optimization problems oriented to Benders decomposition. This yields a generalized version of our previous DeCODe software, renamed DecODe (Decomposition of Optimization problems by Detection).

Third, we incorporate decomposition-based optimization algorithms, including Benders and Lagrangian decompositions into the DecODe software. This extends the capabilities of the software, which now incorporates both structure-based decomposition and decomposition-based solution of optimization problems. The efficacy of our DecODe software is demonstrated by case studies on the solution of some benchmark MINLP problems in comparison to their monolithic solution using state-of-the-art solvers.

References

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

[2] Tang, W., Allman, A., Pourkargar, D. B., & Daoutidis, P. (2018). Optimal decomposition for distributed optimization in nonlinear model predictive control through community detection. Computers & Chemical Engineering, 111, 43-54.

[3] del Rio-Chanona, E. A., Fiorelli, F., & Vassiliadis, V. S. (2016). Automated structure detection for distributed process optimization. Computers & Chemical Engineering, 89, 135-148.

[4] Allman, A., Tang, W., & Daoutidis, P. (2018). DeCODe: A community based algorithm for generating high-quality decoimpositions of optimization problems. Optimization and Engineering, submitted.

[5] Zhang, X., Martin, T., & Newman, M. E. (2015). Identification of core-periphery structure in networks. Physical Review E, 91(3), 032803.