(61z) Stochastic Community Detection: Novel Solution Approach and Application to Sustainable Process Operations

Network theoretic algorithms, such as community detection, have been demonstrated to be powerful tools in accelerating the solution of challenging decision making problems by identifying structure within the underlying optimization formulation to enable exploitation by decomposition solution methods [1] or dimensionality reduction [2]. While these methods are effective when the appropriate underlying graph structure of the optimization problem is known and fixed, many decision making problems, particularly those relevant to process operations and control, require the repeated solution of a problem whose parameters and models are either uncertain or varying in time. This uncertainty/intermittency can manifest in network structures that are also uncertain or time varying. When this occurs, it can be beneficial to identify network structure that occurs robustly over a distribution of graphs (i.e. with different edge weights or node connectivity), rather than one that occurs in a single deterministic network, such that the community detection algorithm doesn’t n ed to be run each time operation is to be optimized. However, while several well-known, greedy algorithms exist to solve the combinatorically-scaling deterministic community detection problem [3], these algorithms don’t easily extend to the stochastic case.

In this work, we propose a novel approach for efficiently solving the stochastic community detection problem. This approach applies a common strategy for stochastic programming problems: using the sample average approximation, introducing copy variables (corresponding to the graph partitioning chosen) for each scenario, and adding non-anticipativity constraints which connect copy variables. This reformulation gives a stochastic programming problem amenable to solution by column generation [4]. Importantly, each independent column generation subproblem is simply the deterministic community detection problem with modularity objective augmented by linear Lagrangean terms. This enables the subproblems to be solved in parallel by efficient solution algorithms such as the Louvain algorithm, with only small modifications required, resulting in a fast, scalable approach to solving the stochastic community detection problem.

To demonstrate the utility of the proposed approach, we consider our team’s recent work in the many-objective operation of a green ammonia production facility [5], which demonstrated that the correlation of cost, emissions, water usage, and safety objectives varied as power cost and emissions profiles evolved in time. In particular, we consider a stochastic objective correlation graph with edge weight distributions generated from various 48-hour operation horizons over a month-long period. We identify groupings of objectives that are optimal with respect to multiple stochastic metrics, including expected value and conditional value at risk, and discuss how this relates to solving the original optimal scheduling problem. We also demonstrate the importance of identifying communities from the stochastic graph, rather than various deterministic graphs.

[1] Allman, A., Tang, W., Daoutidis, P. DeCODe: a community-based algorithm for generating
high-quality decompositions of optimization problems. Optim. Eng. (20), 2019, pp. 1067-1084.
[2] Russell, J.M., Allman, A. Sustainable decision making for chemical process systems via dimen1
sionality reduction of many objective problems. AIChE J. (69), 2023, e17962.
[3] Blondel, V.D., Guillaume, J.-L. ,Lambiotte, R., Lefebvre, E. Fast unfolding of communities in
large networks. J. Stat. Mech. Theor. Exp. (10), 2008, P10008.
[4] Lubbecke, M.E., Desrosiers, J. Selected topics in column generation. Op. Res. (53), 2005, pp.
2-1038.
[5] Allman, A., Russell, J.M. Dynamic objective correlation in many-objective optimization problems: A wind-powered ammonia case study. FOCAPO-CPC, 2023.