Technical Note—Surrogate Constraints and the Strength of Bounds Derived from 0-1 Benders' Partitioning Procedures

Ronald L. Rardin and V. E. Unger
Additional contact information
Ronald L. Rardin: Georgia Institute of Technology, Atlanta, Georgia
V. E. Unger: Georgia Institute of Technology, Atlanta, Georgia

Operations Research, 1976, vol. 24, issue 6, 1169-1175

Abstract: One commonly employed branch-and-bound approach to 0-1 mixed-integer programming problems is to use bounds obtained from the Benders' partitioning of the problem as a device to restrict the enumeration. We investigate the strength of such bounds through the development of a Geoffrion-type strongest surrogate constraint for the Benders' problems. We show that such a surrogate constraint can be developed for the complete Benders' integer problem without explicit enumeration of any of the extreme-point constraints. The bound obtained from this surrogate constraint is then shown to be as strong as that obtained from any of the more common Benders-based approaches, but yet exactly equal to the bound obtained from the linear relaxation of the original mixed-integer program.

Date: 1976
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.24.6.1169 (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:24:y:1976:i:6:p:1169-1175

Access Statistics for this article

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