(136d) Decode: Detection of Communities for Optimization Decomposition

Optimization is a mathematical tool that has become pervasive in process systems engineering for making decisions using mathematical models. In chemical engineering applications, these models often contain integer variables and nonconvex constraints which make the effort required to solve the problem scale poorly with problem size. For such large or difficult to solve optimization problems, a common strategy is to apply a decomposition, whereby the original problem is broken into a series of subproblems with smaller size and reduced computational complexity. Once a decomposition is obtained, there exist many decomposition solution methods that may be applied, the most common of which include a Bender’s decomposition for problems with complicating variables, or a Lagrangean decomposition of problems with complicating constraints. Typically, subproblems are generated in an ad hoc manner governed by the user’s best intuition about the structure of the problem and the type of solution method they wish to employ.

In contrast to the ad hoc approaches typically used, here we present a systematic method for generating decompositions for a generic optimization problem and a software package allowing for the implementation of this method. We call this method and software package DeCODe: the Detection of Communities for Optimization Decomposition. As the name suggests, the method uses communities as the basis for finding subproblems which can be solved efficiently by decomposition solution methods [1]. Community detection is a concept that has been used widely in network theory to find groups within a network which have high modularity; that is, groups which have a statistically high amount of intra-group connectivity and therefore a statistically low amount of inter-group connectivity. To apply this method to an optimization problem, we develop a novel bipartite variable-constraint graph where nodes representing a variable or constraint are connected if the variable appears in the constraint [2]. The communities found in this network represent subproblems in a decomposition which have low connectivity, or coupling, between them, reducing the effort needed by the decomposition solution method. The software package implements the methods described above with minimal input required from the user: only the constraint equations and an initial guess for the variables are required. The software then uses its embedded functions to generate the variable-constraint graph, calculate modularity of different partitions, detect communities, and return which variables or constraints belong to which subproblem. The software package is currently implemented in MATLAB, with plans to extend its use to the Julia programming language in the future.

To document the ability of our software to generate efficient decompositions even when intuition about the problem structure does not exist, we apply it to several problems from the MINLP test library which cannot be solved efficiently without decomposition. In doing so, we demonstrate that the decompositions generated allow for the problem to be solved faster than it could be without a decomposition in cases where the solver for the original problem has trouble improving both the upper bound (best found) solution and lower bound (best possible) solution. We also apply our method to several problems from the literature, such as our previous work which found the optimal design of a combined microgrid and biorefinery system [3], to document cases where intuition matches the decomposition found by our method, and cases where our method finds different decompositions which may admit a more efficient solution. In doing so, we show that our method for finding decompositions is amenable to many of the different decomposition solution methods used by others.

[1] Allman, A., Tang., W., Daoutidis, P. Towards a generic algorithm for identifying high-quality decompositions of optimization problems. Comput. Aided Chem. Eng. 2018, Accepted.
[2] Tang, W., Allman, A., Pourkargar, D.B., Daoutidis, P. Optimal decomposition for distributed optimization in nonlinear model predictive control through community detection. Comput. Chem. Eng. (111). 2018, pp. 43-54.
[3] Allman, A., Daoutidis, P. Optimal design of synergistic renewable fuel and power systems. Renew. Energy (100). 2017, pp. 78-89.