<p>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.</p>

CC BY-SA 3.0
2011-10-20T20:19:43.817Z
Thank you very much, I've managed to get it working. However, I'd like to expand a bit on the original problem. How can I find such a solution to the above diffrence constraint system so that the number of distinct numbers in the solution is maximized?
IceCube
CC BY-SA 3.0
2013-03-08T23:53:08.100Z
*'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
CC BY-SA 3.0
2013-03-09T04:04:28.903Z
No, it's not always zero; it could be negative (in which case the edge of length zero isn't a shortest path).
David Eppstein
CC BY-SA 3.0
2011-10-20T16:01:06.847Z
2011-10-20T16:01:06.847Z
David Eppstein
<p>I want to find a solution to a system of linear inequalities of the following form</p>

<p>\begin{aligned}
a_1 + b &amp;\ge a_2 \\\
\vdots \\\
a_4 + c &amp;\ge a_1
\end{aligned}</p>

<p>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$.</p>

<p>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.</p>

<p>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.</p>

<hr>

<p>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)</p>

CC BY-SA 3.0
2011-10-20T16:19:58.047Z
or you could just check CLRS...
Sasho Nikolov
<ds.algorithms><linear-programming><integer-programming>
Solve a simple system of linear inequalities in natural numbers
IceCube
# Solve a simple system of linear inequalities in natural numbers

(Asked by: username_0 on 2011-10-20)

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)

**Tags:** ds.algorithms, linear-programming, integer-programming

> **Comments:**
> **username_1**: or you could just check CLRS...  

---

## 1 answers

### Answer by username_2 on 2011-10-20. Score: 7

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.

> **Comments:**
> **username_0**: Thank you very much, I've managed to get it working. However, I'd like to expand a bit on the original problem. How can I find such a solution to the above diffrence constraint system so that the number of distinct numbers in the solution is maximized?  
> **username_3**: *'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?  
> **username_2**: No, it's not always zero; it could be negative (in which case the edge of length zero isn't a shortest path).  

---

