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

- Conference: AIChE Annual Meeting
- Year: 2018
- Proceeding: 2018 AIChE Annual Meeting
- Group: Computing and Systems Technology Division
- Session:
- Time:
Monday, October 29, 2018 - 1:27pm-1:46pm

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 ï¬nding subproblems which can be solved eï¬ƒciently by decomposition solution methods [1]. Community detection is a concept that has been used widely in network theory to ï¬nd 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 eï¬€ort 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 eï¬ƒcient 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 eï¬ƒciently 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 bioreï¬nery system [3], to document cases where intuition matches the decomposition found by our method, and cases where our method ï¬nds different decompositions which may admit a more efficient solution. In doing so, we show that our method for ï¬nding 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.