Optimization Online


Duality and a Farkas lemma for integer programs

Jean B. Lasserre (lasserre***at***laas.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society