MHB Understanding the Theorem for Feasible Solutions of Difference Constraints

  • Thread starter Thread starter evinda
  • Start date Start date
AI Thread Summary
The discussion focuses on the theorem related to feasible solutions of difference constraints represented by a graph. Each vertex corresponds to a variable, and edges indicate constraints between these variables, with weights reflecting the bounds. If the graph contains no negative weight cycles, a feasible solution can be derived from the shortest paths from a designated vertex. The Bellman-Ford algorithm is suggested for finding these shortest paths, which leads to determining the values of the variables. The participants verify the feasibility of their solutions against the original constraints, ensuring they meet the necessary conditions.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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.
 
Physics news on Phys.org
evinda said:
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)
 
I like Serena said:
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
 

Attachments

  • diff.png
    diff.png
    10.2 KB · Views: 106
Okay!
So what would the feasible solution be? (Wondering)
 
I like Serena said:
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)
 
evinda said:
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)
 
I like Serena said:
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)
 
evinda said:
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.
 
I like Serena said:
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$.

I like Serena said:
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)
 
  • #10
evinda said:
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)
 
  • #11
I like Serena said:
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)
 
  • #12
evinda said:
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)
 
  • #13
I like Serena said:
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)
 
  • #14
evinda said:
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)
 
  • #15
I like Serena said:
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)
 
  • #16
evinda said:
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)
 
Back
Top