Integer programming, Barvinok's counting algorithm and Gomory relaxations

Jean B. Lasserre (lasserrelaas.fr)

Abstract: 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.

Keywords: Integer programming; generating functions.

Category 1: Integer Programming

Category 2: Combinatorial Optimization (Polyhedra )

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

Download:

Entry Submitted: 06/02/2003
Entry Accepted: 06/02/2003
Entry Last Modified: 10/05/2004

Modify/Update this entry