  


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 Modify/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  