Duality and a Farkas lemma for integer programs

We consider the integer program $\max \{c’ x\,|\,Ax=b,x\in N^n\}$. A formal parallel between linear programming and continuous integration on one side, and discrete summation on the other side, shows that a natural duality for integer programs can be derived from the $Z$-transform and Brion and Vergne’s counting formula. Along the same lines, we also provide a discrete Farkas lemma and show that the existence of a nonnegative integral solution $x\in N^n$ to $Ax=b$ can be tested via a linear program.

Citation

To appear in : Optimization : Structure and Applications (E. Hunt and C.E.M. Pearce, Editors), Applied Optimization Series, Kluwer Academic Publishers, 2003.

Article

Download

View PDF