A Duality Framework 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. In this comparison between linear (LP) and integer (IP) programs, the standard dual LP variables have discrete IP analogues related in a simple manner, and both LP and IP optimal values obey a similar formula. In the same spirit, 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.