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

Many optimization problems of interest for chemical engineers scale poorly with size. This is due
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.