We consider the integer program P -> max {c'x | Ax=y; x\in N^n }. Using the generating function of an associated counting problem, and a generalized residue formula of Brion and Vergne, we explicitly relate P with its continuous linear programming (LP) analogue and provide a characterization of its optimal value. In particular, dual variables $\lambda\in R^m$ have discrete analogues $z\in C^m$, related in a simple manner. Moreover, both optimal values of P and the LP obey the same formula, using z for P and |z| for the LP. One retrieves (and refines) the so-called group-relaxations of Gomory which, in this dual approach, arise naturally from a detailed analysis of a generalized residue formula of Brion and Vergne. Finally, we also provide an explicit formulation of a dual problem P*, an analogue of the dual LP in linear programming.
Citation
Discrete Optimization 1 (2004), pp. 167--187.