  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.

Optimization and Control