(558d) Learning the Structure of Optimization Problems through Stochastic Blockmodeling

The efficient operation and design of process systems is based on the solution of a wide class of large-scale optimization problems. Solving these problems efficiently can be challenging. Application of decomposition-based solution methods can reduce the computational time but a decomposition of the optimization problem itself is a pre-requisite. In general, decomposition-based solution algorithms exploit the underlying structure of the optimization problem [1,2], but the structure is not always apparent. Therefore, learning the underlying structure of the problem is an important first step towards the selection of the most appropriate decomposition-based solution method. In previous work we have proposed the application of community detection on suitable graph representations of optimization problems as a systematic decomposition framework [3]. Although this approach can provide high quality decompositions, it relies on the assumption that the graph has a community structure, which is rather restrictive.

In this work we propose Stochastic Blockmodeling (SBM) and statistical inference as a framework to learn the underlying structure of a optimization problem without any a-priori assumption on the structure of the problem. SBM is a random graph generative model, where the connections among the nodes depend solely on their block affiliation [4]. Therefore, parametric statistical inference can be used to estimate the parameters of the model. Given the graph of an optimization problem and assuming that it is generated by a SBM the inverse problem must be solved: what is the partition of the nodes that generated the observed graph? Efficient approaches for the solution of this problem utilizing maximum likelihood estimation or Bayesian inference will be discussed, along with a general framework for linking the graph structure with standard distributed or hierarchical decomposition-based solution algorithms such as Benders and Lagrangean ones.

We apply this approach to benchmark optimization problems from MINLP and MORG libraries and we show that the proposed approach can indeed uncover complex block structures of optimization problems. The estimated structure is used as the basis for the application of decomposition-based solution algorithms which are shown to reach an optimum or bound estimate in reduced computational time compared to monolithic approaches. Finally, we present a general software platform for automated block structure detection and decomposition-based solution.

References:

[1]. Conejo, A.J., Castillo, E., Minguez, R. and Garcia-Bertrand, R., 2006. Decomposition Techniques in Mathematical Programming: Engineering and Science Applications. Springer Science & Business Media.

[2]. Daoutidis, P., Tang, W. and Allman, A., 2019. Decomposition of control and optimization problems by network structure: Concepts, methods, and inspirations from biology. AIChE Journal, 65(10), p.e16708.

[3]. Allman, A., Tang, W. and Daoutidis, P., 2019. DeCODe: a community-based algorithm for generating high-quality decompositions of optimization problems. Optimization and Engineering, 20(4), pp.1067-1084.

[4]. Peixoto, T.P., 2019. Bayesian stochastic blockmodeling. Advances in network clustering and blockmodeling, pp.289-332.