A Convergent Duality Theory for Integer Programming

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.