Stochastic blockmodeling for learning the structure of optimization problems
Stochastic blockmodeling for learning the structure of optimization problems
复制标题
用于学习优化问题结构的随机块建模
DOI：
10.1002/aic.17415
复制
发表时间：
2021
期刊：
影响因子：
3.7
通讯作者：
Daoutidis, Prodromos
中科院分区：
文献类型：
--
作者：
Mitrai, Ilias;Tang, Wentao;Daoutidis, Prodromos
优化问题的基于分解的求解算法取决于问题的潜在潜在块结构。目前缺乏检测这种结构的方法。在本文中，我们提出随机块建模（SBM）作为学习通用优化问题中底层块结构的系统框架。 SBM 是一种生成图模型，其中节点属于某些区块，节点之间的互连随机依赖于它们的区块从属关系。因此，通过参数统计推断，可以估计优化问题背后的互连模式。对于基准优化问题，我们表明 SBM 可以揭示底层块结构，并且估计块可以用作基于分解的解决方案算法的基础，该算法可以在减少计算时间的情况下达到最佳或界限估计。最后，我们提出了一个通用软件平台，用于遵循分布式和分层优化方法的自动块结构检测和基于分解的解决方案。
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.