Cross Decomposition Applied to Integer Programming Problems: Duality Gaps and Convexification in Parts

Kaj Holmberg
Additional contact information
Kaj Holmberg: Linköping Institute of Technology, Linköping, Sweden

Operations Research, 1994, vol. 42, issue 4, 657-668

Abstract: We study 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 Lagrangian 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 Lagrangian relaxation. However, cross decomposition can be used to automatically 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 Lagrangian relaxation.

Keywords: integer programming; algorithms: duality gaps in decomposition; mathematics; convexity: duality gaps for integer programming (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.42.4.657 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:42:y:1994:i:4:p:657-668

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().