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/2003
Entry Accepted: 04/26/2003
Entry Last Modified: 07/09/2003

Modify/Update this entry