- Duality and a Farkas lemma for integer programs Jean B. Lasserre (lasserrelaas.fr) Abstract: 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. Keywords: Integer programming; generating function; Farkas lemma Category 1: Integer Programming Category 2: Integer Programming (Other ) Category 3: Combinatorial Optimization (Polyhedra ) Citation: To appear in : Optimization : Structure and Applications (E. Hunt and C.E.M. Pearce, Editors), Applied Optimization Series, Kluwer Academic Publishers, 2003. Download: [PDF]Entry Submitted: 04/26/2003Entry Accepted: 04/26/2003Entry Last Modified: 07/09/2003Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.