Integer programming, Barvinok's counting algorithm and Gomory relaxations. (Q1417591): Difference between revisions

Barvinok's algorithm to count the integral points of a convex rational polytope can be used to solve integer programs. In this paper an upper bound on the optimal value of the integer program \(P\) is derived from Barvinok's formula. A condition for the upper bound being equal to the optimal value of \(P\) is also given. Finally, the author applies this result to the Gomory relaxation of \(P\) (which is also an integer program) to derive a relationship between Barvinok's result and Gomory relaxations.