Integer programming, Barvinok’s counting algorithm and Gomory relaxations

We propose an algorithm based on Barvinok's counting algorithm for P -> max {c'x | Ax <=b; x in Z^n}. It runs in time polynomial in the input size of P when n is fixed, and under a condition on c, provides the optimal value of P. We also relate Barvinok's counting formula and Gomory relaxations.


Oper. Res. Letters. 32 (2003), pp. 133--137.