I am looking for an algorithm for checking the satisfiability (with natural values) of a set of inequalities made of variables and natural numbers, for example: $u < v, u \leq z, 3 \leq v$.


In this paper, <http://boole.stanford.edu/pub/sefnp.pdf> , there's the following claim in the second page:



> 
> "Then the conjunction is satisfiable if and only if the graph contains a cycle of positive weight, i.e., one whose labels add up to a positive integer."
> 
> 
> 


The graph it mentions consists of a node for each variable in the inequalities, plus one extra node for the number $0$. Then, for each inequality, we add an edge from node $x$ to node $y$ with weight $i$ if the inequality is written as $x + i \leq y$.


Is the claim true? I can't work out any example, indeed, I think that what makes sense is exactly the opposite: the conjunction is not satisfiable if and only if the graph contains a cycle of positive weight. (it would mean that $u + k \leq u$ for some node $u$ with positive $k$).


Btw, any other algorithm regarding this problem is welcome.



Algorithm for satisfiability of inequalities.
This looks very much like the "difference constraints" that are explored in the big white textbook "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein. The graph seems about the same and there is a theorem about negative weight cycles. I suggest you will find what you need there.


