(41f) Decode – Automated Structure-Based Decomposition and Decomposition-Based Solution of Optimization Problems
Recently, a systematic method of decomposing optimization problems based on detecting the community structures in the corresponding network representations  has been proposed, with a software implementation called DeCODe (Detection of Communities for Optimization Decomposition) . 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., ), 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.
 Jalving, J., Cao, Y., & Zavala, V. M. (2019). Graph-based modeling and simulation of complex systems. Computers & Chemical Engineering, 125, 134-154.
 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.
 del Rio-Chanona, E. A., Fiorelli, F., & Vassiliadis, V. S. (2016). Automated structure detection for distributed process optimization. Computers & Chemical Engineering, 89, 135-148.
 Allman, A., Tang, W., & Daoutidis, P. (2018). DeCODe: A community based algorithm for generating high-quality decoimpositions of optimization problems. Optimization and Engineering, submitted.
 Zhang, X., Martin, T., & Newman, M. E. (2015). Identification of core-periphery structure in networks. Physical Review E, 91(3), 032803.
This paper has an Extended Abstract file available; you must purchase the conference proceedings to access it.
Do you already own this?
Log In for instructions on accessing this content.
|AIChE Graduate Student Members||Free|
|AIChE Undergraduate Student Members||Free|