Difference Constraints And Shortest‐Path - rFronteddu/general_wiki GitHub Wiki
In the general linear-programming problem, we are given an m x n matrix A, and m-vector b, and an n-vector c. We wish to find a vector x of n elements that maximizes the objective function
$$ \sum_{i=1}^{n} c_ix_i $$
subject to the m constraints given by Ax $\leq$ b.
If we know that we can cast a given problem as a polynomial-sized linear-programming problem, then we immediately have a polynomial-time algorithm to solve the problem. Second, faster algorithms exist for many special case of linear programming. Sometimes, we don't really care about the objective function; we just wish to find any feasible solution, that is, any vector x that satisfies Ax $\leq$ b, or to determine that no feasible solution exists.
Systems of difference constraints
In a system of difference constraints, each row of the linear-programming matrix A contains one 1 and one -1, and all other entries of A are 0. Thus, the constraints given by Ax $\leq$ b are a set of m difference constraints involving n unknowns, in which each constraint is a simple linear inequality of the form
$$x_j-x_i\leq b_k$$
Where 1 $\leq$ i, j $\leq$ n, i $\neq$ j, and 1 $leq$ k $leq$ m.
To clarify, imagine to have a matrix of 1 and -1 multiplied by a column of variables $x_1$,... $x_5$ that has to be $\leq$ of another column.
A = [
1 -1 0 0 0
1 0 0 0 -1
...
0 0 0 -1 1
]
x= [
x1
x2
x3
x4
x5
]
b = [
0
-1
...
-3
]
Would Result in a system o 5 equations:
x1 - x2 <= 0
x1 - x5 <= -1
...
x5- x4 <= -3
Let x = $(x_1, x_2,...,x_n)$ be a solution to a system $Ax\leq b$ of difference constraints, and let d be any constant. Then $x+d=(x_1+d,x_2+d,...,x_n+d$ is a solution to $Ax\leq b$ as well.
Systems of difference constraints occur in many different applications. For example, if we apply an adhesive that takes 2 hours to set at time $x_1$ and we have to wait until it sets to install a part at time $x_2$, then we have the constraint that $x_2 \geq x_1 + 2$ or equivalently that $x_1-x_2 \leq -2$.
Constraints graphs
We can interpret systems of difference constraints from a graph-theoretic point of view. In a system $Ax \leq b$ of difference constraints, we view the m x n linear-programming matrix A as the transpose of an incidence matrix for a graph with n vertices and m edges. Each vertex $v_i$ in the graph for i=1,2,...,n corresponds to one of the n unknown variables $x_i$. Each directed edge in the graph corresponds to one of the m inequalities involving two unknowns.
More formally, given a system $Ax \leq b$ of difference constraints, the corresponding constraint graph is a weighted, directed graph G = (V,E), where
- V = { $v_0, v_1,...,v_n$ }
- E = { $(v_i, v_j)$ : $x_j-x_i \leq b_k$ is a constant } U { $(v_0, v_1), (v_0, v_2), ..., (v_0, v_n)$ }
The constraint graph contains the additional vertex $v_0$ to guarantee that the graph ha some vertex which can reach all other vertices. The vertex set V consists of a vertex $v_i$ for each unknown $x_i$ plus an additional vertex $v_0$. The edge set E contains an edge for each difference constraint, plus an edge $(v_0, v_i)$ for each unknown $x_i$.
If $x_j-x_i \leq b_k$ is a difference constraint, then the weight of edge $(v_i, v_j)$ is $w(v_i, v_j)=b_k$. The weight of each edge leaving $v_0$ is 0.
Given such a system, and its corresponding constraint graph, if G contains no negative-weight cycles, then
$$x=(\delta(v_0,v_1), \delta(v_0,v_2), ...,\delta(v_0,v_n)$$
is a feasible solution for the system. if G contains a negative-weight cycle, then there is no feasible solution for the system (we can find a solution by finding the s-p weights in the corresponding constraint graph).
Solving systems of difference constraints
From the previous theorem we can use Bellman-Ford to solve a system of difference constraints.
A system of difference constraints with m constraints of n unknowns produces a graph with n+1 vertices and n+m edges. Thus, using Bellman Ford we can solve the system in O((n+1)(n+m)) time, the algorithm can be modified to solve the problem in O(n*m).