# (120e) Identification of Optimization Decomposition Structures Via Community Detection Algorithms

- Conference: AIChE Annual Meeting
- Year: 2017
- Proceeding: 2017 AIChE Annual Meeting
- Group: Computing and Systems Technology Division
- Session:
- Time:
Monday, October 30, 2017 - 1:54pm-2:15pm

to the presence of nonlinear, nonconvex terms in many chemical models, including, for example,

bilinear terms in mass balance constraints, nonconvex power functions of variables for capital costs,

or reaction equilibria terms. To solve these complex optimization problems, a classical method

widely applied in process systems engineering is to seek a decomposition, namely to separate the

original problems into subproblems of smaller sizes with reduced computational complexity by

first removing some complicating variables and constraints, and then coordinating the subproblems

through a master problem or primal-dual approaches [1, 2].

As a motivating example, consider our previous work which determined the optimal design

of a plant which couples biofuel and renewable energy production [3]. The original optimization

formulation was a very large (~60,000 variables) and computationally intractable mixed integer

nonlinear program (MINLP). However, the overall plant consisted of two subsystems, the biofuel

producing subsystem and the energy producing subsystems, which shared a few variables. As such,

the original problem was decomposed into a much smaller (~700 variables) nonlinear program

(NLP) which determined the optimal biofuel plant design, and a large mixed integer *linear* program

(MILP) which determined the optimal renewable energy plant design. A master problem decided

values for the three variables shared by the two systems. This approach made the optimization

problem tractable, solving the problem within a reasonable (<10%) optimality gap.

For a general optimization problem, one cannot determine an optimal decomposition intuitively

as in the motivating example. As such, this work proposes a generic automated approach to

finding subnetworks within optimization problems using community detection algorithms. Such an

approach has been proven useful in the control-relevant decomposition of chemical plant dynamic

networks for distributed model predictive control [4, 5]. For the purpose of optimization, the

problem is converted to a novel bipartite graph with one category of nodes representing equations

and the other category of nodes representing variables. Community detection algorithms, e.g.

spectral clustering or fast unfolding, are then used to identify communities (i.e. clusters of equations

and variables) which are connected by a minimum number of shared variables or constraints.

The framework allows for the incorporation of other considerations; for example, ensuring that

the communities are tightly interacting amongst themselves, or requiring that the most difficult

nonconvex equations all appear in the same community which is made as small as possible. We apply

the proposed method to various optimization problems from existing test libraries, and document

its capability to systematically generate efficient decompositions whenever they are warranted by

the structure of the problem.

[1] Conejo, A.J., Castillo, E., Minguez, R., and Garcia-Bertrand, R. Decomposition techniques

in mathematical programming: Engineering and science applications (2006). Springer.

[2] Grossmann, I.E. Advances in mathematical programming models for enterprise-wide opti-

mization. Comput. Chem. Eng., 47(2012), pp. 2-18.

[3] Allman, A., and Daoutidis, P. Optimal design of synergistic renewable fuel and power sys-

tems. Renew. Energy, 100(2017), pp. 78-89.

[4] Tang, W. and Daoutidis, P. Hybrid distributed/hierarchical control architecture design. 20th

IFAC World Congress, (2017), accepted.

[5] Pourkargar, D.B., Almansoori, A., and Daoutidis, P. Distributed model predictive control

of process networks: Impact of control architecture. 20th IFAC World Congress, (2017), accepted.