Stochastic blockmodeling for learning the structure of optimization problems

Decomposition-based solution algorithms for optimization problems depend on the underlying latent block structure of the problem. Methods for detecting this structure are currently lacking. In this article, we propose stochastic blockmodeling (SBM) as a systematic framework for learning the underlying block structure in generic optimization problems. SBM is a generative graph model in which nodes belong to some blocks and the interconnections among the nodes are stochastically dependent on their block affiliations. Hence, through parametric statistical inference, the interconnection patterns underlying optimization problems can be estimated. For benchmark optimization problems, we show that SBM can reveal the underlying block structure and that the estimated blocks can be used as the basis for decomposition-based solution algorithms which can reach an optimum or bound estimates in reduced computational time. Finally, we present a general software platform for automated block structure detection and decomposition-based solution following distributed and hierarchical optimization approaches.

Automated summary

This article proposes using stochastic blockmodeling (SBM) to learn the underlying block structure in generic optimization problems and estimates the interconnection patterns through parametric statistical inference for decomposition-based solution algorithms. Furthermore, a general software platform is developed for automated block structure detection and following distributed and hierarchical optimization approaches.