Solving system of linear inequalities

I am trying to solve a system of inequalities in the following form:
$\ x_i - x_j \leq w $

I know these inequalities can be solved using Bellman-Ford algorithm. But there is also another condition. I want to find the solution that maximizes $\ x_n - x_1$

As far as I know the default Bellman-Ford algorithm minimizes it. How do I do that?

The textbook Bellman-Ford algorithm will indeed minimize the span of the variables: $max_i(x_i) - min_i(x_i)$. It involves adding a supernode and 0-weight edges from the supernode to every other nodes in the graph. This is probably what the op is referring to.

To maximize $x_n - x_1$, as usual, convert the difference constraints to edges. However, we will not add the super node and its 0 weight edges. Instead, just run Bellman-Ford using the node for $x_1$ as source:

• If negative cycle is detected, the constraints can't be satisfied.

• The result distance $x_n$ will maximize $x_n - x_1$. If $x_n$ is infinity, that means $x_1$ and $x_n$ can be arbitrarily far apart.

Now let's see why it works.

Why do the $x$s satisfy the constraints?

Proof: By triangle inequality, same as the textbook Bellman-Ford method. I won't repeat it here.

Why will the result distance $x_n$ maximize $x_n - x_1$?

Proof: Consider the shortest path $p = (v_1, v_2,...,v_n)$ from $v_1$ to $v_n$, the path corresponds to the following set of constraints:

      $x_2-x_1\leq w[1,2]$

      $x_3-x_2\leq w[2,3]$

            ...

      $x_n-x_{n-1}\leq w[n-1,n]$

Summing the constraints, we obtain:

      $x_n-x_1\leq\sum_2^n w[i-1,i]=w(p)$

That is, in any solution that satisfies the constraints, $x_n - x_1$ cannot be greater than $w(p)$, the weight of the shortest path from $v_1$ to $v_n$. As Bellman-Ford sets $x_n-x_1$ to the shortest path value, this implies $x_n-x_1$ is as large as possible.

StackExchange Computer Science Q#11445, answer score: 4