Difference constraints

In integer programming, difference constraints is a problem where we’re interested in satisfying a system of difference equations, i.e.,:

$$x_1-x_3\le 3$$ $$x_2-x_1\le -1$$ $$x_3-x_2\le -1$$ $$x_3-x_4\le 1$$ $$x_4-x_1\le 4$$

Our goal is to find values of $x_i$ such that a solution exists, or to show that no solution exists. We can use traditional linear programming techniques, like the simplex method. We can also model this as a shortest path problem and solve with the Bellman-Ford algorithm.

As a shortest path problem

We can model each $x$ as a node in a directed, weighted graph. We construct a constraint graph with this in mind, where we have one vertex per variable. We also define a pseudo-start $v_0$ that connects to all nodes. We have one edge per constraint.

Then, we assign weights. The weight from the pseudo-start to all nodes is set to 0. Then:

$$w(v_i,v_j)=b_k$$

for all constraints in the form:

$$x_j-x_i\le b_k$$

i.e., for an equation $x_1-x_3\le 3$, we model it as an edge to $x_1$ from $x_3$ with a weight of 3.

Some relevant theorems:

• If $G$ has no negative weight cycle, then $x_1=\delta (v_0,v_1),\cdots ,x_n=\delta (v_0,v_n)$ is a feasible solution.
• If $G$ has a negative weight cycle, then there is no feasible solution.

Then, we run Bellman-Ford to find the shortest path from $v_0$ to all $v_1,\cdots ,v_n$. This gives us the solution, or it reports a negative cycle.