2
$\begingroup$

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)

$\endgroup$
  • 6
    $\begingroup$ or you could just check CLRS... $\endgroup$ – Sasho Nikolov Oct 20 '11 at 16:19
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – IceCube Oct 20 '11 at 20:19
  • $\begingroup$ '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? $\endgroup$ – BlueRaja - Danny Pflughoeft Mar 8 '13 at 23:53
  • $\begingroup$ No, it's not always zero; it could be negative (in which case the edge of length zero isn't a shortest path). $\endgroup$ – David Eppstein Mar 9 '13 at 4:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.