论文标题
大规模线性编程问题的分解，包含通过准确证书链接变量和约束的分解
Decomposition of Large Scale Linear Programming Problems Containing both Linking Variables and Constraints via Accuracy Certificates
论文作者
论文摘要
存在几种众所周知的大规模线性编程分解方法。弯曲者分解，涵盖了一些少量变量将原本可分离的子问题连接起来的情况。 Dantzig-Wolfe的分解和拉格朗日分解，其中一些限制条件将原本可分离的子问题连接起来，最后是TJ Van Roy的“交叉分解”，源自TJ Van Roy，这使一个人能够处理链接约束和链接变量，从本质上讲，通过在本质上交流了Benders和Lagrangian Decompostions和Lagrangian Decompostions之间的交流。在本文中，我们提出了一种新颖的替代交叉分解替代方法，该替代方案既涉及链接约束和通过应用黑框，基于次级基于NELGORITH的精确证书（例如NERGORITHM）来链接变量。
Several well known large scale linear programming decomposition methodologies exist. Benders Decomposition, which covers the case where some small subset of variables link the otherwise separable subproblems. Dantzig-Wolfe decomposition and Lagrangian decompositions, which cover the case where some few constraints link the otherwise separable subproblems, and finally the "Cross-Decomposition" originating from TJ Van Roy which enables one to deal with both linking constraints and linking variables by essentially alternating iteratively between the Benders and the Lagrangian Decomposition. In this paper we present a novel alternative to Cross-decomposition that deals with both linking constraints and linking variables through the application of accuracy certificates for black-box, sub-gradient based algorithms such as NERML.
