(468g) Constrained Network Structure Detection for Decomposing Optimization Problems

Algorithms from the field of network theory have been used to identify insightful community and core-periphery structures in networks using techniques such as modularity maximization [1] and statistical inference [2]. These techniques have seen general applications in a wide range of networks such as those used to analyze social interactions [3] and protein-protein interactions [4]. Of particular interest in process systems engineering is the use of these methods to understand and exploit the structure of optimization problems to make them amenable for solving using decomposition-based approaches [5]. This approach works very well for decomposition solution methods that have no limitations on the characteristics of master- and sub-problems, such as Lagrangian decomposition. However, many decomposition solution methods for mixed-integer nonlinear programs (MINLPs) such as nonlinear branch-and-price [6], which requires all nonlinearities to show up in subproblems and all variables linking master and subproblems to be integer, or generalized Benders’ decomposition [7], which requires all integer variables to be within the master problem, impart inherent constraints on the structure required to utilize these approaches. Unfortunately, the most effective algorithms for structure detection of networks are inherently unconstrained, requiring the development of new tools to be able to detect and exploit the appropriate structures for the aforementioned decomposition solution approaches.

In this work, we propose a novel approach to efficiently solving the constrained structure detection problem with a focus on cardinality and edge-based constraints that correspond to the structure limitations for certain decomposition solution approaches described previously. To achieve this, we note that any constraints to the structure detection problem are inherently “complicating” - if they were to be removed from the problem, it could be solved much easier using existing unconstrained structure detection approaches. As such, we utilize a column generation approach[8] whereby the subproblem is an unconstrained structure detection problem with an objective function augmented by dual terms, and the master problem chooses between generated network partitions and updates dual variables corresponding to the additional cardinality and edge-based constraints. We demonstrate that it is reasonably straightforward to incorporate the additional dual terms when using popular structure detection algorithms, such as Newman’s spectral algorithm or the Louvain algorithm for community detection, and Borgatti–Everett’s core-periphery model [9] for core-periphery detection. This results in a fast and scalable approach to solving the constrained community detection problem and identifying structures amenable to solving using the decomposition solution approaches described previously.

The efficacy of the proposed approach is shown by applying it to a set of benchmark problems whose structures are known to be amenable to solution using a nonlinear branch-and-price algorithm [6]. These include problems on trim loss minimization, capacity planning, integrated wastewater network design, and the multi-scenario design of multi-product batch plants. We generate the relevant graphs for each case study and detect the network structure that reveals the core linear complicating constraints connected to the distinct communities representing the subproblems via integer variable edges. We compare various structure detection approaches, including community and core-periphery detection on variable and constraint graph representations. Importantly, we also demonstrate that the computational time required to detect the requisite structure is insignificant when compared to the time required to solve the underlying optimization problems.

References

[1] M. E. J. Newman. “Modularity and community structure in networks”. In: Proceedings of the National Academy of Sciences 103.23 (2006), pp. 8577–8582. doi: 10.1073/pnas.0601602103. eprint: https://www.pnas.org/doi/pdf/10.1073/pnas.0601602103. url: https://www.pnas.org/doi/abs/10.1073/pnas.0601602103.

[2] Tiago P. Peixoto. “Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models”. In: Phys. Rev. E 89 (2014), p. 012804. doi: 10.1103/PhysRevE.89.012804. url: https://link.aps.org/doi/10.1103/PhysRevE.89.012804.

[3] Vincent Blondel et al. “Fast Unfolding of Communities in Large Networks”. In: Journal of Statistical Mechanics Theory and Experiment 2008 (2008). doi: 10.1088/1742-5468/2008/10/P10008.

[4] Pall Jonsson et al. “Cluster analysis of networks generated through homology: Automatic identification of important protein communities involved in cancer metastasis”. In: BMC bioinformatics 7 (2006), p. 2. doi: 10.1186/1471-2105-7-2.

[5] Andrew Allman, Wentao Tang, and Prodromos Daoutidis. “DeCODe: a community-based algorithm for generating high-quality decompositions of optimization problems”. In: Optimization and Engineering 20 (2019). doi: 10.1007/s11081-019-09450-5.

[6] Andrew Allman and Qi Zhang. Branch-and-Price for a Class of Nonconvex Mixed-Integer Nonlinear Programs. 2020. doi: 10.1007/s10898-021-01027-w. url: https://doi.org/10.1007/s10898-021-01027-w.

[7] Arthur M Geoffrion. “Generalized Benders decomposition”. In: J. Optim. Theor. Appl. 10 (1972), pp. 237–260.

[8] Marco L¨ubbecke and Jacques Desrosiers. “Selected Topics in Column Generation”. In: Operations Research 53 (2005), pp. 1007–. doi: 10.1287/opre.1050.0234.

[9] Stephen P Borgatti and Martin G Everett. “Models of core/periphery structures”. In: Social Networks 21.4 (2000), pp. 375–395. issn: 0378-8733. doi: https://doi.org/10.1016/S0378-8733(99)00019-2. url: https://www.sciencedirect.com/science/article/pii/S0378873399000192.