Cross decomposition applied to integer programming problems: Duality gaps and convexification in parts

The paper studies the lower bounds on the optimal objective function value of linear pure integer programming problems obtainable by the convexification in parts that results from using Benders’ or cross decomposition, and the best lower bounds obtainable by the convexification resulting from Lagrangean relaxation together with subgradient optimization or Dantzig-Wolfe decomposition. A comparison shows that generalized Benders’ and generalized cross decomposition yield the best of these bounds, while ordinary Benders’ decomposition yields bounds that are sometimes better and sometimes worse than those of Lagrangean relaxation. However, cross decomposition can be used to automaticlly get the best of the two bounds. The conclusion of this paper is that cross decomposition can be useful for getting good lower bounds for pure integer programming problems, bounds that can be made better than those of the frequently used Langrangean relaxation.