# Solve a simple system of linear inequalities in natural numbers

I want to find a solution to a system of linear inequalities of the following form

\begin{aligned} a_1 + b &\ge a_2 \\\ \vdots \\\ a_4 + c &\ge a_1 \end{aligned}

where $a_i \in \mathbb N \setminus \{0\}$ and $b,c \in \mathbb Z$. All inequalities consist of exactly two variables and one free factor. All $a_i$ appear as they are, and have no coefficient other than $1$.

The goal is to find a solution (perhaps more than one, but not necessarily), or declare the system as not having one. Such a solution would be vastly preferable to any linear programming ones.

I do remember some algorithm based on constructing a graph and then launching Floyd-Warshall algorithm could solve a similar problem, but I'm not sure.

EDIT: Problem expansion - how can I find such a solution that the number of distinct integers in the solution is maximized (the default Bellman-Ford behavior minimizes it)

• or you could just check CLRS... – Sasho Nikolov Oct 20 '11 at 16:19

Construct a graph with one vertex per variable, and one extra vertex $s$. Make an edge from $s$ to all other vertices, of length zero. For each inequality $a_i + c \ge a_j$, make an edge of length $c$ from $a_i$ to $a_j$. Then if your graph has a negative-length cycle, your inequalities have no solution, and if it does not have a negative-length cycle then the distance from $s$ to each vertex gives a solution. You can use Floyd or Bellman–Ford or any other shortest path algorithm that can allow negative weights.
• 'the distance from s to each vertex gives a solution" - Wouldn't the distance from s to each vertex be 0, since you added an edge of length 0 from s to every other vertex? – BlueRaja - Danny Pflughoeft Mar 8 '13 at 23:53