Simplex method with artificial variables
Author
Hey folks. I've been looking for a fast way to detect collisions between rectangular prisms, so now I'm trying the simplex method. Probably not the fastest, but my idea is to use the method's phase 1 to just determine if a solution is possible. I'm having a little trouble as I'm new to this. So here go my equations:
(k1) a + (k2) b + (k3) c + (k4) d + (k5) e + (k6) f = k7
(k8) a + (k9) b + (k10) c + (k11) d + (k12) e + (k13) f = k14
(k15) a + (k16) b + (k17) c + (k18) d + (k19) e + (k20) f = k21
0<=a,b,c,d,e,f <=1
where k1...k21 are just constants.
Now as I understand it, I have to use 6 equations with slack variables like this:
a + x1 = 1
b + x2 = 1
c + x3 = 1
d + x4 = 1
e + x5 = 1
f + x6 = 1
And change the equalities by adding artificial variables(I didn't put all the K's for brevity):
a + b + c + d + e + f + y1 = k7
a + b + c + d + e + f + y2 = k14
a + b + c + d + e + f + y3 = k21
So far I think I've done it right. I read that I now have to use the simplex to minimize y1 + y2 + y3, and if their sum is different from zero after all the iterations, no solution is possible. The problem is, how do I build my simplex table? In the documentation I have, the artificial variables are equal to the number of equations so they form an identity matrix, but this isn't the case here. Thanks for reading.
I'm wondering if we're talking about the same simplex.
The simplex is a problem of maximization.
When you have an equation you have to maximize under certain constraints, you can use the simplex algorithm.
For finding the minimum of f(X), you can use the trick of searching for the maximum of -f(X), otherwise it won't work.
So I don't see what you're doing in your post, i don't recognize even the canonical forms of the constraints wich are absolutely necessary.
If you can be clearer maybe I can help.
Also, simplex is long to achieve, especialy that there are some tricks to be sure to find a solution(cause it will not always find even there is one), but the process will be longer, it is a kind of secure but longer path.
I don't recommend you using that but of course you might have your reasons.
Cheers, Jeff.
The simplex is a problem of maximization.
When you have an equation you have to maximize under certain constraints, you can use the simplex algorithm.
For finding the minimum of f(X), you can use the trick of searching for the maximum of -f(X), otherwise it won't work.
So I don't see what you're doing in your post, i don't recognize even the canonical forms of the constraints wich are absolutely necessary.
If you can be clearer maybe I can help.
Also, simplex is long to achieve, especialy that there are some tricks to be sure to find a solution(cause it will not always find even there is one), but the process will be longer, it is a kind of secure but longer path.
I don't recommend you using that but of course you might have your reasons.
Cheers, Jeff.
Author
Ok, the problem I have to solve is the following:
(k1) a + (k2) b + (k3) c + (k4) d + (k5) e + (k6) f = k7
(k8) a + (k9) b + (k10)c + (k11)d + (k12)e + (k13)f = k14
(k15)a + (k16)b + (k17)c + (k18)d + (k19)e + (k20)f = k21
0<=a,b,c,d,e,f <=1
where k1...k21 are just constants.
And I have to maximize a+b+c+d+e+f.
Now my question is, how do I express the above problem in canonical form so I that can use the simplex on it?
So if I want to take care of the constraint a,b,c,d,e,f <=1, I have to add slack variables like this, right?
a + x1 = 1
b + x2 = 1
c + x3 = 1
d + x4 = 1
e + x5 = 1
f + x6 = 1
And for the equalities, I have to add artificial variables y1, y2 and y3:
a + b + c + d + e + f + y1 = k7
a + b + c + d + e + f + y2 = k14
a + b + c + d + e + f + y3 = k21
Now if I try to build the simplex table, I get this:
k k k k k k 1 0 0 0 0 0 0 0 0 k7
k k k k k k 0 1 0 0 0 0 0 0 0 k14
k k k k k k 0 0 1 0 0 0 0 0 0 k21
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1
0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1
0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1
0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1
0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1
0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1
The first 6 columns reprensent variables a to f, the next 3 y1,y2,y3 and the last 6, x1 to x6.
Have I done things right? And if so, is that the canonical form?
EDIT: the forum ate my formatting
EDIT2: About using the simplex, I do it because I don't have much knowledge in 3d and so far it's the fastest method I know.
[Edited by - Seifer on August 6, 2004 7:42:51 PM]
(k1) a + (k2) b + (k3) c + (k4) d + (k5) e + (k6) f = k7
(k8) a + (k9) b + (k10)c + (k11)d + (k12)e + (k13)f = k14
(k15)a + (k16)b + (k17)c + (k18)d + (k19)e + (k20)f = k21
0<=a,b,c,d,e,f <=1
where k1...k21 are just constants.
And I have to maximize a+b+c+d+e+f.
Now my question is, how do I express the above problem in canonical form so I that can use the simplex on it?
So if I want to take care of the constraint a,b,c,d,e,f <=1, I have to add slack variables like this, right?
a + x1 = 1
b + x2 = 1
c + x3 = 1
d + x4 = 1
e + x5 = 1
f + x6 = 1
And for the equalities, I have to add artificial variables y1, y2 and y3:
a + b + c + d + e + f + y1 = k7
a + b + c + d + e + f + y2 = k14
a + b + c + d + e + f + y3 = k21
Now if I try to build the simplex table, I get this:
k k k k k k 1 0 0 0 0 0 0 0 0 k7
k k k k k k 0 1 0 0 0 0 0 0 0 k14
k k k k k k 0 0 1 0 0 0 0 0 0 k21
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1
0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1
0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1
0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1
0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1
0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1
The first 6 columns reprensent variables a to f, the next 3 y1,y2,y3 and the last 6, x1 to x6.
Have I done things right? And if so, is that the canonical form?
EDIT: the forum ate my formatting
EDIT2: About using the simplex, I do it because I don't have much knowledge in 3d and so far it's the fastest method I know.
[Edited by - Seifer on August 6, 2004 7:42:51 PM]
In the simplex, the constraints are inequalities, and you have equalities :
(k1) a + (k2) b + (k3) c + (k4) d + (k5) e + (k6) f = k7
(k8) a + (k9) b + (k10)c + (k11)d + (k12)e + (k13)f = k14
(k15)a + (k16)b + (k17)c + (k18)d + (k19)e + (k20)f = k21
This nevers occurs cause you don't need simplex here, Gauss Pivot will be enough.
In the case you had inequalities like :
(k1) a + (k2) b + (k3) c + (k4) d + (k5) e + (k6) f <= k7
(k8) a + (k9) b + (k10)c + (k11)d + (k12)e + (k13)f <= k14
(k15)a + (k16)b + (k17)c + (k18)d + (k19)e + (k20)f <= k21
then you intruce "space variables"(here A, B, C) so that you have equalities :
(k1) a + (k2) b + (k3) c + (k4) d + (k5) e + (k6) f + A = k7
(k8) a + (k9) b + (k10)c + (k11)d + (k12)e + (k13)f + B = k14
(k15)a + (k16)b + (k17)c + (k18)d + (k19)e + (k20)f + C = k21
Express it like this
A = k7 - (k1) a - (k2) b - (k3) c - (k4) d - (k5) e - (k6) f
B = k14 - (k8) a - (k9) b - (k10)c - (k11)d - (k12)e - (k13)f
C = k21 - (k15)a - (k16)b - (k17)c - (k18)d - (k19)e - (k20)f
a,b,c,d,e,f are called in base variables cause they are in the equation to maximize, and A,B,C are called out of base variables.
Then the goal of the simplex is to select a variable in the base that will go out and to select one of the out of base to put it in base.
There are many heuristiques to select the variables, some safes, other fast but unsafer.
The simplex stops when all the coefficients of the variables that are in base are NEGATIVE.
Note that the simplex can find solutions but it may not be optimal !!! To prove an optimality of a solution, you must use the DUAL, wich is minimization algorithm based on the simplex.
So, does it help and ask me if something is unclear.
PS : Sorry for my english and the scientific terms, I'm french.
Cheers, Jeff.
(k1) a + (k2) b + (k3) c + (k4) d + (k5) e + (k6) f = k7
(k8) a + (k9) b + (k10)c + (k11)d + (k12)e + (k13)f = k14
(k15)a + (k16)b + (k17)c + (k18)d + (k19)e + (k20)f = k21
This nevers occurs cause you don't need simplex here, Gauss Pivot will be enough.
In the case you had inequalities like :
(k1) a + (k2) b + (k3) c + (k4) d + (k5) e + (k6) f <= k7
(k8) a + (k9) b + (k10)c + (k11)d + (k12)e + (k13)f <= k14
(k15)a + (k16)b + (k17)c + (k18)d + (k19)e + (k20)f <= k21
then you intruce "space variables"(here A, B, C) so that you have equalities :
(k1) a + (k2) b + (k3) c + (k4) d + (k5) e + (k6) f + A = k7
(k8) a + (k9) b + (k10)c + (k11)d + (k12)e + (k13)f + B = k14
(k15)a + (k16)b + (k17)c + (k18)d + (k19)e + (k20)f + C = k21
Express it like this
A = k7 - (k1) a - (k2) b - (k3) c - (k4) d - (k5) e - (k6) f
B = k14 - (k8) a - (k9) b - (k10)c - (k11)d - (k12)e - (k13)f
C = k21 - (k15)a - (k16)b - (k17)c - (k18)d - (k19)e - (k20)f
a,b,c,d,e,f are called in base variables cause they are in the equation to maximize, and A,B,C are called out of base variables.
Then the goal of the simplex is to select a variable in the base that will go out and to select one of the out of base to put it in base.
There are many heuristiques to select the variables, some safes, other fast but unsafer.
The simplex stops when all the coefficients of the variables that are in base are NEGATIVE.
Note that the simplex can find solutions but it may not be optimal !!! To prove an optimality of a solution, you must use the DUAL, wich is minimization algorithm based on the simplex.
So, does it help and ask me if something is unclear.
PS : Sorry for my english and the scientific terms, I'm french.
Cheers, Jeff.
Author
Quote:Original post by funkeejeffounet
In the simplex, the constraints are inequalities, and you have equalities :
(k1) a + (k2) b + (k3) c + (k4) d + (k5) e + (k6) f = k7
(k8) a + (k9) b + (k10)c + (k11)d + (k12)e + (k13)f = k14
(k15)a + (k16)b + (k17)c + (k18)d + (k19)e + (k20)f = k21
This nevers occurs cause you don't need simplex here, Gauss Pivot will be enough.
In the case you had inequalities like :
(k1) a + (k2) b + (k3) c + (k4) d + (k5) e + (k6) f <= k7
(k8) a + (k9) b + (k10)c + (k11)d + (k12)e + (k13)f <= k14
(k15)a + (k16)b + (k17)c + (k18)d + (k19)e + (k20)f <= k21
then you intruce "space variables"(here A, B, C) so that you have equalities :
(k1) a + (k2) b + (k3) c + (k4) d + (k5) e + (k6) f + A = k7
(k8) a + (k9) b + (k10)c + (k11)d + (k12)e + (k13)f + B = k14
(k15)a + (k16)b + (k17)c + (k18)d + (k19)e + (k20)f + C = k21
Express it like this
A = k7 - (k1) a - (k2) b - (k3) c - (k4) d - (k5) e - (k6) f
B = k14 - (k8) a - (k9) b - (k10)c - (k11)d - (k12)e - (k13)f
C = k21 - (k15)a - (k16)b - (k17)c - (k18)d - (k19)e - (k20)f
a,b,c,d,e,f are called in base variables cause they are in the equation to maximize, and A,B,C are called out of base variables.
Then the goal of the simplex is to select a variable in the base that will go out and to select one of the out of base to put it in base.
There are many heuristiques to select the variables, some safes, other fast but unsafer.
The simplex stops when all the coefficients of the variables that are in base are NEGATIVE.
Note that the simplex can find solutions but it may not be optimal !!! To prove an optimality of a solution, you must use the DUAL, wich is minimization algorithm based on the simplex.
So, does it help and ask me if something is unclear.
PS : Sorry for my english and the scientific terms, I'm french.
Cheers, Jeff.
Yes, but you forgot these constraints:
0<=a,b,c,d,e,f <=1
I can't use the Gauss pivot because of them. Or if I can, I don't know how.
How would you add these constraints to the simplex above?
I managed to code the simplex algorithm, but it's no use if I can't formulate my problem in the canonical form.
By the way, could you give me an example where the solution isn't optimal even after the end of the algorithm? I've read the algo always comes up with the optimal solution, so I'm intrigued.
Oh, and I'm french too, mais je te gage que je me ferais bannir si je parlais Français.
Ok for the constraint where a,b,c,d,e,f >= 0, this is not a problem as the simplex works with positive values, this is a implicit constraint. For the other one(<=1), just add each of them as a constraint like this :
a <= 1
a + D = 1
D = 1 - a
do the same for the others and here you go.
The simplex usually works, but there are some things your attention must go to :
- There are degenerate cases where the simplex will loop cause he will never find the solution(this can be detected thought)
- If you choose badly your variables you might loop too, but there is a rule that let you always finish
- The simplex might find a solution that won't be optimal. Check for "dual simplex" on google. But the result will respect the constraint thought
I don't have any examples here for non optimality but if you insist I'll search for one. But you can sincerely believe me, that's why the dual method exists, it is to check the solution's optimality.
Cheers, Jeff
PS : ca fait plaisir de voir un chti français ici ;)
a <= 1
a + D = 1
D = 1 - a
do the same for the others and here you go.
The simplex usually works, but there are some things your attention must go to :
- There are degenerate cases where the simplex will loop cause he will never find the solution(this can be detected thought)
- If you choose badly your variables you might loop too, but there is a rule that let you always finish
- The simplex might find a solution that won't be optimal. Check for "dual simplex" on google. But the result will respect the constraint thought
I don't have any examples here for non optimality but if you insist I'll search for one. But you can sincerely believe me, that's why the dual method exists, it is to check the solution's optimality.
Cheers, Jeff
PS : ca fait plaisir de voir un chti français ici ;)
Author
Quote:Original post by funkeejeffounet
Ok for the constraint where a,b,c,d,e,f >= 0, this is not a problem as the simplex works with positive values, this is a implicit constraint. For the other one(<=1), just add each of them as a constraint like this :
a <= 1
a + D = 1
D = 1 - a
do the same for the others and here you go.
The simplex usually works, but there are some things your attention must go to :
- There are degenerate cases where the simplex will loop cause he will never find the solution(this can be detected thought)
- If you choose badly your variables you might loop too, but there is a rule that let you always finish
- The simplex might find a solution that won't be optimal. Check for "dual simplex" on google. But the result will respect the constraint thought
I don't have any examples here for non optimality but if you insist I'll search for one. But you can sincerely believe me, that's why the dual method exists, it is to check the solution's optimality.
Cheers, Jeff
PS : ca fait plaisir de voir un chti français ici ;)
Yeah I did that already, just look at the second post after the bump.
I've read a bit about the dual simplex, from what I understand it applies to situations where the right hand side is negative?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
