Understanding the Theorem for Feasible Solutions of Difference Constraints

[evinda]

Hello! (Wave)

We construct the graph of a system of difference constraints like that:
Each vertex $v_i$ corresponds to one of the unknown variables.
Between the vertices $v_i$ and $v_j$ there is an edge iff $x_j-x_i \leq b_k$.
The weight of the edge $(v_i,v_j)$ is $b_k$.
At the graph of a system of difference constraints,we add an additional vertex $v_0$ and the edges $(v_0,v_1), (v_0,v_2), \dots, (v_0,v_n)$ with weight $0$.

Could you explain me the following theorem? (Thinking)

Let $G$ the graph,that corresponds to the problem $Ax \leq b$.If $G$ does not contain negative weight cycles,then a feasible solution of $Ax \leq b$ is this:
$$x=(\delta(v_0,v_1),\delta(v_0,v_2), \dots, \delta(v_0,v_n))$$
If $G$ contains negative weight cycles ,then $Ax \leq b$ has no feasible solution.

 

[I like Serena]

Hello! (Wave)

We construct the graph of a system of difference constraints like that:
Each vertex $v_i$ corresponds to one of the unknown variables.
Between the vertices $v_i$ and $v_j$ there is an edge iff $x_j-x_i \leq b_k$.
The weight of the edge $(v_i,v_j)$ is $b_k$.
At the graph of a system of difference constraints,we add an additional vertex $v_0$ and the edges $(v_0,v_1), (v_0,v_2), \dots, (v_0,v_n)$ with weight $0$.

Could you explain me the following theorem? (Thinking)

Let $G$ the graph,that corresponds to the problem $Ax \leq b$.If $G$ does not contain negative weight cycles,then a feasible solution of $Ax \leq b$ is this:
$$x=(\delta(v_0,v_1),\delta(v_0,v_2), \dots, \delta(v_0,v_n))$$
If $G$ contains negative weight cycles ,then $Ax \leq b$ has no feasible solution.

Hi! (Smile)

Can you give us an example with, say, 2 variables? (Wondering)

 

[evinda]

Hi! (Smile)

Can you give us an example with, say, 2 variables? (Wondering)

This is an example of a system of difference constraints:

$$x_1-x_2 \leq 0$$
$$x_1-x_5 \leq -1$$
$$x_2-x_5 \leq 1$$
$$x_3-x_1 \leq 5$$
$$x_4-x_1 \leq 4$$
$$x_4-x_3 \leq -1$$
$$x_5-x_3 \leq -3$$
$$x_5-x_4 \leq -3$$

The graph of this system of difference constraints is the following:

View attachment 3139

 

[I like Serena]

Okay!
So what would the feasible solution be? (Wondering)

 

[evinda]

Okay!
So what would the feasible solution be? (Wondering)

So...do I have to apply now the algorithm of Bellman-Ford,to find $d[v], \forall v \in V$ and then the feasible solution will be:

$$x=(d[v_1],d[v_2], \dots , d[v_5])$$

? (Thinking)

 

[I like Serena]

So...do I have to apply now the algorithm of Bellman-Ford,to find $d[v], \forall v \in V$ and then the feasible solution will be:

$$x=(d[v_1],d[v_2], \dots , d[v_5])$$

? (Thinking)

Yes.
Or else you could do it based on common sense, which should boil down to the same thing. (Wink)

 

[evinda]

Yes.
Or else you could do it based on common sense, which should boil down to the same thing. (Wink)

How could I do it based on common sense? (Thinking)

 

[I like Serena]

How could I do it based on common sense? (Thinking)

Try to find the shortest path from $v_0$ to $v_1$.
The direct path takes $0$.
Via $v_5$ it takes $-1$, which is better.

Can you find a better path yet? (Wondering)Btw, you don't need a perfect solution if you only want to understand the theorem.
Just a set of fairly low-cost paths will do to see how it works.

 

[evinda]

Try to find the shortest path from $v_0$ to $v_1$.
The direct path takes $0$.
Via $v_5$ it takes $-1$, which is better.

Can you find a better path yet? (Wondering)

I found a better path: $v_0 \to v_4 \to v_5 \to v_1$ , which weight is $-4$.

Btw, you don't need a perfect solution if you only want to understand the theorem.
Just a set of fairly low-cost paths will do to see how it works.

I just wanted to understand the theorem, but I haven't understood yet, why $x=(\delta(v_0,v_1), \delta(v_0,v_2), \dots , \delta(v_0,v_n))$ is a solution of $Ax \leq b$.. (Sweating) Could you explain it further to me? (Thinking)

 

[I like Serena]

I found a better path: $v_0 \to v_4 \to v_5 \to v_1$ , which weight is $-4$.

There you go! (Smile)

I just wanted to understand the theorem, but I haven't understood yet, why $x=(\delta(v_0,v_1), \delta(v_0,v_2), \dots , \delta(v_0,v_n))$ is a solution of $Ax \leq b$.. (Sweating) Could you explain it further to me? (Thinking)

We have just found that $\delta(v_0,v_1)=-4$.
That means that we are supposed to have a feasible solution with $x_1=-4$.
Can you also find the (or at least reasonable) values for the other variables?

Do they form what is called a feasible solution? (Wondering)

 

[evinda]

We have just found that $\delta(v_0,v_1)=-4$.
That means that we are supposed to have a feasible solution with $x_1=-4$.
Can you also find the (or at least reasonable) values for the other variables?

Do they form what is called a feasible solution? (Wondering)

I found the following shortest paths:

$v_0 \to v_3 \to v_4 \to v_5 \to v_2$, which weight is $-3$

$v_0 \to v_3$, which weight is $0$

$v_0 \to v_3 \to v_4$, which weight is $-1$

$v_0 \to v_3 \to v_4 \to v_5$, which weight is $-4$

Am I right? (Thinking)

So.. according to the theorem, a feasible solution is: $(-4,-3,0,-1,-4)$.. Can I just verify it, replacing $x_i, i \in \{ 1, \dots, 5 \}$ at the inequalities? (Thinking)

 

[I like Serena]

I found the following shortest paths:

$v_0 \to v_3 \to v_4 \to v_5 \to v_2$, which weight is $-3$

$v_0 \to v_3$, which weight is $0$

$v_0 \to v_3 \to v_4$, which weight is $-1$

$v_0 \to v_3 \to v_4 \to v_5$, which weight is $-4$

Am I right? (Thinking)

I think so. (Nod)

So.. according to the theorem, a feasible solution is: $(-4,-3,0,-1,-4)$.. Can I just verify it, replacing $x_i, i \in \{ 1, \dots, 5 \}$ at the inequalities? (Thinking)

Yes. That is what it means.
Does it check out? (Wondering)

 

[evinda]

Yes. That is what it means.
Does it check out? (Wondering)

Isn't it like that?

$$x_1=-4$$

$$x_2=-3$$

$$x_3=0$$

$$x_4=-1$$

$$x_5=-4$$

$$x_1-x_2=-1 \leq 0 $$

$$x_1-x_5=0 \geq -1$$

$$x_2-x_5=1 \leq 1$$

$$x_3-x_1=4 \leq 5$$

$$x_4-x_1=3 \leq 4$$

$$x_4-x_3=-1 \leq -1$$

$$x_5-x_3=-4 \leq -3$$

$$x_5-x_4=-3 \leq -3$$

The inequality $x_1-x_5 \leq -1$ doesn't hold... (Sweating) Have I done something wrong? (Thinking)

 

[I like Serena]

Isn't it like that?

The inequality $x_1-x_5 \leq -1$ doesn't hold... (Sweating) Have I done something wrong? (Thinking)

Looks that way.
Can you find a better path for $x_1$ then? (Wondering)

 

[evinda]

Looks that way.
Can you find a better path for $x_1$ then? (Wondering)

I found a better path for $x_1$: $v_0 \to v_3 \to v_4 \to v_5 \to v_1$, which weight is equal to $-5$.

So, $x_1=-5$

Now:

$$x_1-x_2=-8 \leq 0$$

$$x_1-x_5=-1 \leq -1$$

$$x_3-x_1=5 \leq 5$$

$$x_4-x_1=4 \leq 4$$

Right? (Thinking)

 

[I like Serena]

I found a better path for $x_1$: $v_0 \to v_3 \to v_4 \to v_5 \to v_1$, which weight is equal to $-5$.

So, $x_1=-5$

Right? (Thinking)

Right! (Yes)

I guess you understand the theorem now. (Clapping)