A Convergent Duality Theory for Integer Programming

David E. Bell and Jeremy F. Shapiro
Additional contact information
David E. Bell: Cambridge University, Cambridge, England
Jeremy F. Shapiro: Massachusetts Institute of Technology, Cambridge, Massachusetts

Operations Research, 1977, vol. 25, issue 3, 419-434

Abstract: We present a constructive procedure for generating a finite sequence of increasingly stronger dual problems to a given integer programming problem. The last dual problem in the sequence yields an optimal solution to the integer programming problem. We show that this dual problem approximates the convex hull of the feasible integer solutions in a neighborhood of the optimal solution it finds. The theory is applicable to any bounded integer programming problem with rational data.

Date: 1977
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.25.3.419 (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:25:y:1977:i:3:p:419-434

Access Statistics for this article

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