A discrete Farkas lemma

Abstract

Given $A\in {\mathbb{Z}}^{m\times n}$ and $b\in {\mathbb{Z}}^m$, we consider the issue of existence of a nonnegative integral solution $x\in {\mathbb{N}}^n$ to the system of linear equations $Ax=b$. We provide a discrete and explicit analogue of the celebrated Farkas lemma for linear systems in ${\mathbb{R}}^n$ and prove that checking existence of integral solutions reduces to solving an explicit linear programming problem of fixed dimension, known in advance.

9 pages; ICCSA 2003 conference, Montreal, May 2003