Is there some methods to solve equations with MIN operation?
in [Math]
|
Prev: 6.- Conjecture .
Next: Name for matrix
From: Xu Wang on 30 Jul 2010 04:44 On Jul 29, 8:48 pm, "Rob Pratt" <Rob.Pr...(a)sas.com> wrote: > "Xu Wang" <wangxu.n...(a)gmail.com> wrote in message > > news:55fd3ca6-30d3-40f5-830f-68e507c1b8d9(a)s9g2000yqd.googlegroups.com... > On Jul 29, 1:38 am, Ray Vickson <RGVick...(a)shaw.ca> wrote: > > > > > On Jul 28, 10:19 am, Xu Wang <wangxu.n...(a)gmail.com> wrote: > > > > Hi everyone, > > > > I have to solve a set of equations with MIN operation. > > > > MIN operation: > > > For an equation MIN{x1, x2, ..., xn} = a, "a" is the minimal value > > > among x1 to xn. > > > > A set of equations with MIN operation is like: > > > > MIN{x1, x2} = b > > > MIN{x3, x4} = c > > > MIN{x2+x3, x5} = d > > > You can formulate and solve this as a *linear programming* problem > > (assuming a, b, c, ... are all >= 0): > > minimize x1 + x2 +x3 + x4 + x5 + x6 > > subject to > > x6 = x2 + x3, > > x1 >= b, > > x2 >= b, > > x3 >= c, > > x4 >= c, > > x5 >= d, > > x6 >= d. > > > R.G. Vickson > > > > ..... > > > > Is it possible to solve or partially solve the equations. I mean is > > > there some algorithms or methods to solve the value of some variables? > > > Could anyone give me a hint about which part of mathematics does this > > > problem belong to? > > > > Thank you in advance. > > > > Best regards, > > > Xu > > I tried to solve it in linear programming the following example. > > MIN{x1+x2, x3+x4} = 5 > MIN{x2, x3+x4} = 3 > > as > > x2 >= 3 > x3+x4 >= 5 > x1+x2 >= 5 > > the answer is > > x1 = 1.2177 > x2 = 3.1823 > x3 = 2.5000 > x4 = 2.5000 > > But I think this is not the answer, because > 1. for MIN{x2, x3+x4} = 3, one of x2 and (x3+x4) must be 3, > 2. it is easy to see that x2 = 3. > > Xu > > --- > > Your x1 + x2 does not satisfy the thrid constraint. > > If I minimize x1 + x2 + x3 + x4, I get (x1,x2,x3,x4) = (2,3,5,0). I cannot get this answer. Although I am trying to find more information, I am new to LP and Matlab. The following is my code f = [1;1;1;1;0;0] A = [ 0 -1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 -1]; b = [-3;-5;-5]; Aeq = [ -1 -1 0 0 1 0 0 0 -1 -1 0 1]; Beq = [0;0] lb = zeros(6,1) [x, fval, exitflag, output, lambda] = linprog(f,A,b,Aeq,Beq,lb); After adding Aeq and Beq, I got x = 1.1475 3.8525 2.5000 2.5000 5.0000 5.0000 This answer satisfy the constraints, but I can not get your answer. Xu
From: Torsten Hennig on 30 Jul 2010 01:39 > On Jul 29, 8:48 pm, "Rob Pratt" <Rob.Pr...(a)sas.com> > wrote: > > "Xu Wang" <wangxu.n...(a)gmail.com> wrote in message > > > > > news:55fd3ca6-30d3-40f5-830f-68e507c1b8d9(a)s9g2000yqd.g > ooglegroups.com... > > On Jul 29, 1:38 am, Ray Vickson <RGVick...(a)shaw.ca> > wrote: > > > > > > > > > On Jul 28, 10:19 am, Xu Wang > <wangxu.n...(a)gmail.com> wrote: > > > > > > Hi everyone, > > > > > > I have to solve a set of equations with MIN > operation. > > > > > > MIN operation: > > > > For an equation MIN{x1, x2, ..., xn} = a, "a" > is the minimal value > > > > among x1 to xn. > > > > > > A set of equations with MIN operation is like: > > > > > > MIN{x1, x2} = b > > > > MIN{x3, x4} = c > > > > MIN{x2+x3, x5} = d > > > > > You can formulate and solve this as a *linear > programming* problem > > > (assuming a, b, c, ... are all >= 0): > > > minimize x1 + x2 +x3 + x4 + x5 + x6 > > > subject to > > > x6 = x2 + x3, > > > x1 >= b, > > > x2 >= b, > > > x3 >= c, > > > x4 >= c, > > > x5 >= d, > > > x6 >= d. > > > > > R.G. Vickson > > > > > > ..... > > > > > > Is it possible to solve or partially solve the > equations. I mean is > > > > there some algorithms or methods to solve the > value of some variables? > > > > Could anyone give me a hint about which part of > mathematics does this > > > > problem belong to? > > > > > > Thank you in advance. > > > > > > Best regards, > > > > Xu > > > > I tried to solve it in linear programming the > following example. > > > > MIN{x1+x2, x3+x4} = 5 > > MIN{x2, x3+x4} = 3 > > > > as > > > > x2 >= 3 > > x3+x4 >= 5 > > x1+x2 >= 5 > > > > the answer is > > > > x1 = 1.2177 > > x2 = 3.1823 > > x3 = 2.5000 > > x4 = 2.5000 > > > > But I think this is not the answer, because > > 1. for MIN{x2, x3+x4} = 3, one of x2 and (x3+x4) > must be 3, > > 2. it is easy to see that x2 = 3. > > > > Xu > > > > --- > > > > Your x1 + x2 does not satisfy the thrid constraint. > > > > If I minimize x1 + x2 + x3 + x4, I get > (x1,x2,x3,x4) = (2,3,5,0). > > I cannot get this answer. Although I am trying to > find more > information, I am new to LP and Matlab. The following > is my code > > f = [1;1;1;1;0;0] > A = [ 0 -1 0 0 0 0 > 0 0 0 0 -1 0 > 0 0 0 0 0 -1]; > b = [-3;-5;-5]; > Aeq = [ -1 -1 0 0 1 0 > 0 0 -1 -1 0 1]; > Beq = [0;0] > lb = zeros(6,1) > [x, fval, exitflag, output, lambda] = > linprog(f,A,b,Aeq,Beq,lb); > > After adding Aeq and Beq, I got > > x = > > 1.1475 > 3.8525 > 2.5000 > 2.5000 > 5.0000 > 5.0000 > > This answer satisfy the constraints, but I can not > get your answer. > > Xu Both x-vectors are solutions of the LP problem since they satisfy the constraints and minimize the objective function. The fact that the first solution gives a solution to the min-problem and the second does not shows that LP-formulation and min-problem are not equivalent. Best wishes Torsten.
From: Xu Wang on 30 Jul 2010 06:06 On Jul 29, 6:55 pm, Ray Vickson <RGVick...(a)shaw.ca> wrote: > On Jul 29, 2:32 am, Xu Wang <wangxu.n...(a)gmail.com> wrote: > > > > > On Jul 29, 1:38 am, Ray Vickson <RGVick...(a)shaw.ca> wrote: > > > > On Jul 28, 10:19 am, Xu Wang <wangxu.n...(a)gmail.com> wrote: > > > > > Hi everyone, > > > > > I have to solve a set of equations with MIN operation. > > > > > MIN operation: > > > > For an equation MIN{x1, x2, ..., xn} = a, "a" is the minimal value > > > > among x1 to xn. > > > > > A set of equations with MIN operation is like: > > > > > MIN{x1, x2} = b > > > > MIN{x3, x4} = c > > > > MIN{x2+x3, x5} = d > > > > You can formulate and solve this as a *linear programming* problem > > > (assuming a, b, c, ... are all >= 0): > > > minimize x1 + x2 +x3 + x4 + x5 + x6 > > > subject to > > > x6 = x2 + x3, > > > x1 >= b, > > > x2 >= b, > > > x3 >= c, > > > x4 >= c, > > > x5 >= d, > > > x6 >= d. > > > > R.G. Vickson > > > > > ..... > > > > > Is it possible to solve or partially solve the equations. I mean is > > > > there some algorithms or methods to solve the value of some variables? > > > > Could anyone give me a hint about which part of mathematics does this > > > > problem belong to? > > > > > Thank you in advance. > > > > > Best regards, > > > > Xu > > > I tried to solve it in linear programming the following example. > > > MIN{x1+x2, x3+x4} = 5 > > MIN{x2, x3+x4} = 3 > > > as > > > x2 >= 3 > > x3+x4 >= 5 > > x1+x2 >= 5 > > > the answer is > > > x1 = 1.2177 > > x2 = 3.1823 > > x3 = 2.5000 > > x4 = 2.5000 > > > But I think this is not the answer, because > > 1. for MIN{x2, x3+x4} = 3, one of x2 and (x3+x4) must be 3, > > 2. it is easy to see that x2 = 3. > > > Xu > > You are correct, and I removed my message; my newsreader/poster > removed it, but some others might not. The problem arises from the > presence of summed x_j terms in the 'mins'; without that, the method > would be OK. > > Your problem CAN be correctly formulated as a _mixed-integer_ > programming problem. Look at the first equation min{x1+x2, x3+x4} = 5. > Suppose we have known upper bounds U on the x_j; that is, let's assume > we want x_j <= U for all j. We can sometimes say a priori what some > reasonable bounds are, but if not, just specify some 'large' number. > So, I'll take U = 100. Then x1 + x2 <= 200 and x3 + x4 <= 200. Now let > y1 be a binary variable (y1 = 0 or 1) and write the following: > x1 + x2 >= 5 > x3 + x4 >= 5 > x1 + x2 <= 5*y1 + 200*(1-y1) > x3 + x4 <= 5*(1-y1) + 200*y1. > > If y1 = 0 these say x1+x2>=5,x1+x2<=5 (hence x1+x2=5) and x3+x4 >=5, > x3+x4 <= 200 (hence 5 <= x3+x4 <=200). Certainly, x1+x2 is the minimum > of x1+x2 and x3+x4, and this minimum = 5. Similarly if y1 = 1 we have > x3+x4 = 5 and 5 <= x1+x2 <=200. > > You can do the same thing for the other 'min'. Finally, some mixed- > integer codes need an objective, so let's just maximize or minimize > something, such as the sum of the x_j. > > Here is the final formulation, done in LINGO 11.0 > MIN = x1+x2+x3+x4; > x1 + x2 >= 5; > x3 + x4 >= 5; > x1 + x2 <= 5*y1 + 200*(1-y1); > x3 + x4 <= 5*(1-y1) + 200*y1; > x2 >= 3; > x3+x4 >= 3; > x2 <= 3*y2 + 100*(1-y2); > x3+x4 <= 3*(1-y2) + 200*y2; > @BIN(y1); > @BIN(y2); > > The solution is: > Global optimal solution found. > Objective value: 10.00000 > Objective bound: 10.00000 > Infeasibilities: 0.000000 > Extended solver steps: 0 > Total solver iterations: 0 > > Variable Value Reduced Cost > X1 2.000000 0.000000 > X2 3.000000 0.000000 > X3 0.000000 0.000000 > X4 5.000000 0.000000 > Y1 1.000000 0.000000 > Y2 1.000000 0.000000 > > So: x1 = 2, x2 = 3, x3 = 0 and x4 = 5. > > If a good mixed-integer programming code fails to find a feasible > solution, that would mean that the original problem is infeasible. > > R.G. Vickson Thank you for your help. Your approach is right. Unfortunately, I don't have LINGO and only have Matlab. Therefore, I have to find how to represent the following equations in Matlab;) x3+x4 <= 3*(1-y2) + 200*y2; @BIN(y1); Xu
From: Ray Vickson on 30 Jul 2010 12:20 On Jul 30, 3:06 am, Xu Wang <wangxu.n...(a)gmail.com> wrote: > On Jul 29, 6:55 pm, Ray Vickson <RGVick...(a)shaw.ca> wrote: > > > > > On Jul 29, 2:32 am, Xu Wang <wangxu.n...(a)gmail.com> wrote: > > > > On Jul 29, 1:38 am, Ray Vickson <RGVick...(a)shaw.ca> wrote: > > > > > On Jul 28, 10:19 am, Xu Wang <wangxu.n...(a)gmail.com> wrote: > > > > > > Hi everyone, > > > > > > I have to solve a set of equations with MIN operation. > > > > > > MIN operation: > > > > > For an equation MIN{x1, x2, ..., xn} = a, "a" is the minimal value > > > > > among x1 to xn. > > > > > > A set of equations with MIN operation is like: > > > > > > MIN{x1, x2} = b > > > > > MIN{x3, x4} = c > > > > > MIN{x2+x3, x5} = d > > > > > You can formulate and solve this as a *linear programming* problem > > > > (assuming a, b, c, ... are all >= 0): > > > > minimize x1 + x2 +x3 + x4 + x5 + x6 > > > > subject to > > > > x6 = x2 + x3, > > > > x1 >= b, > > > > x2 >= b, > > > > x3 >= c, > > > > x4 >= c, > > > > x5 >= d, > > > > x6 >= d. > > > > > R.G. Vickson > > > > > > ..... > > > > > > Is it possible to solve or partially solve the equations. I mean is > > > > > there some algorithms or methods to solve the value of some variables? > > > > > Could anyone give me a hint about which part of mathematics does this > > > > > problem belong to? > > > > > > Thank you in advance. > > > > > > Best regards, > > > > > Xu > > > > I tried to solve it in linear programming the following example. > > > > MIN{x1+x2, x3+x4} = 5 > > > MIN{x2, x3+x4} = 3 > > > > as > > > > x2 >= 3 > > > x3+x4 >= 5 > > > x1+x2 >= 5 > > > > the answer is > > > > x1 = 1.2177 > > > x2 = 3.1823 > > > x3 = 2.5000 > > > x4 = 2.5000 > > > > But I think this is not the answer, because > > > 1. for MIN{x2, x3+x4} = 3, one of x2 and (x3+x4) must be 3, > > > 2. it is easy to see that x2 = 3. > > > > Xu > > > You are correct, and I removed my message; my newsreader/poster > > removed it, but some others might not. The problem arises from the > > presence of summed x_j terms in the 'mins'; without that, the method > > would be OK. > > > Your problem CAN be correctly formulated as a _mixed-integer_ > > programming problem. Look at the first equation min{x1+x2, x3+x4} = 5.. > > Suppose we have known upper bounds U on the x_j; that is, let's assume > > we want x_j <= U for all j. We can sometimes say a priori what some > > reasonable bounds are, but if not, just specify some 'large' number. > > So, I'll take U = 100. Then x1 + x2 <= 200 and x3 + x4 <= 200. Now let > > y1 be a binary variable (y1 = 0 or 1) and write the following: > > x1 + x2 >= 5 > > x3 + x4 >= 5 > > x1 + x2 <= 5*y1 + 200*(1-y1) > > x3 + x4 <= 5*(1-y1) + 200*y1. > > > If y1 = 0 these say x1+x2>=5,x1+x2<=5 (hence x1+x2=5) and x3+x4 >=5, > > x3+x4 <= 200 (hence 5 <= x3+x4 <=200). Certainly, x1+x2 is the minimum > > of x1+x2 and x3+x4, and this minimum = 5. Similarly if y1 = 1 we have > > x3+x4 = 5 and 5 <= x1+x2 <=200. > > > You can do the same thing for the other 'min'. Finally, some mixed- > > integer codes need an objective, so let's just maximize or minimize > > something, such as the sum of the x_j. > > > Here is the final formulation, done in LINGO 11.0 > > MIN = x1+x2+x3+x4; > > x1 + x2 >= 5; > > x3 + x4 >= 5; > > x1 + x2 <= 5*y1 + 200*(1-y1); > > x3 + x4 <= 5*(1-y1) + 200*y1; > > x2 >= 3; > > x3+x4 >= 3; > > x2 <= 3*y2 + 100*(1-y2); > > x3+x4 <= 3*(1-y2) + 200*y2; > > @BIN(y1); > > @BIN(y2); > > > The solution is: > > Global optimal solution found. > > Objective value: 10.00000 > > Objective bound: 10.00000 > > Infeasibilities: 0.000000 > > Extended solver steps: 0 > > Total solver iterations: 0 > > > Variable Value Reduced Cost > > X1 2.000000 0.000000 > > X2 3.000000 0.000000 > > X3 0.000000 0.000000 > > X4 5.000000 0.000000 > > Y1 1.000000 0.000000 > > Y2 1.000000 0.000000 > > > So: x1 = 2, x2 = 3, x3 = 0 and x4 = 5. > > > If a good mixed-integer programming code fails to find a feasible > > solution, that would mean that the original problem is infeasible. > > > R.G. Vickson > > Thank you for your help. Your approach is right. > > Unfortunately, I don't have LINGO and only have Matlab. Therefore, I > have to find how to represent the following equations in Matlab;) If you are a student you can download a free version of LINGO (or LINDO) from Lindo Corp. It would be able to handle modest-sized problems having no more than about two hundred variables (but a considerably smaller number of integer variables). Alternatively, you can formulate and solve the problem using the built-in EXCEL Solver; this comes bundled with every copy of EXCEL, but you may need to "install" it. Again, the default version is limited to a few hundred variables and a smaller number of integer variables. R.G. Vickson > > x3+x4 <= 3*(1-y2) + 200*y2; > @BIN(y1); > > Xu
From: Xu Wang on 2 Aug 2010 04:54
On Jul 29, 6:55 pm, Ray Vickson <RGVick...(a)shaw.ca> wrote: > On Jul 29, 2:32 am, Xu Wang <wangxu.n...(a)gmail.com> wrote: > > > > > On Jul 29, 1:38 am, Ray Vickson <RGVick...(a)shaw.ca> wrote: > > > > On Jul 28, 10:19 am, Xu Wang <wangxu.n...(a)gmail.com> wrote: > > > > > Hi everyone, > > > > > I have to solve a set of equations withMINoperation. > > > > >MINoperation: > > > > For an equationMIN{x1, x2, ..., xn} = a, "a" is the minimal value > > > > among x1 to xn. > > > > > A set of equations withMINoperationis like: > > > > >MIN{x1, x2} = b > > > >MIN{x3, x4} = c > > > >MIN{x2+x3, x5} = d > > > > You can formulate and solve this as a *linear programming* problem > > > (assuming a, b, c, ... are all >= 0): > > > minimize x1 + x2 +x3 + x4 + x5 + x6 > > > subject to > > > x6 = x2 + x3, > > > x1 >= b, > > > x2 >= b, > > > x3 >= c, > > > x4 >= c, > > > x5 >= d, > > > x6 >= d. > > > > R.G. Vickson > > > > > ..... > > > > > Is it possible to solve or partially solve the equations. I mean is > > > > there some algorithms or methods to solve the value of some variables? > > > > Could anyone give me a hint about which part of mathematics does this > > > > problem belong to? > > > > > Thank you in advance. > > > > > Best regards, > > > > Xu > > > I tried to solve it in linear programming the following example. > > >MIN{x1+x2, x3+x4} = 5 > >MIN{x2, x3+x4} = 3 > > > as > > > x2 >= 3 > > x3+x4 >= 5 > > x1+x2 >= 5 > > > the answer is > > > x1 = 1.2177 > > x2 = 3.1823 > > x3 = 2.5000 > > x4 = 2.5000 > > > But I think this is not the answer, because > > 1. forMIN{x2, x3+x4} = 3, one of x2 and (x3+x4) must be 3, > > 2. it is easy to see that x2 = 3. > > > Xu > > You are correct, and I removed my message; my newsreader/poster > removed it, but some others might not. The problem arises from the > presence of summed x_j terms in the 'mins'; without that, the method > would be OK. > > Your problem CAN be correctly formulated as a _mixed-integer_ > programming problem. Look at the first equationmin{x1+x2, x3+x4} = 5. > Suppose we have known upper bounds U on the x_j; that is, let's assume > we want x_j <= U for all j. We can sometimes say a priori what some > reasonable bounds are, but if not, just specify some 'large' number. > So, I'll take U = 100. Then x1 + x2 <= 200 and x3 + x4 <= 200. Now let > y1 be a binary variable (y1 = 0 or 1) and write the following: > x1 + x2 >= 5 > x3 + x4 >= 5 > x1 + x2 <= 5*y1 + 200*(1-y1) > x3 + x4 <= 5*(1-y1) + 200*y1. > > If y1 = 0 these say x1+x2>=5,x1+x2<=5 (hence x1+x2=5) and x3+x4 >=5, > x3+x4 <= 200 (hence 5 <= x3+x4 <=200). Certainly, x1+x2 is the minimum > of x1+x2 and x3+x4, and this minimum = 5. Similarly if y1 = 1 we have > x3+x4 = 5 and 5 <= x1+x2 <=200. > > You can do the same thing for the other 'min'. Finally, some mixed- > integer codes need an objective, so let's just maximize or minimize > something, such as the sum of the x_j. > > Here is the final formulation, done in LINGO 11.0MIN= x1+x2+x3+x4; > x1 + x2 >= 5; > x3 + x4 >= 5; > x1 + x2 <= 5*y1 + 200*(1-y1); > x3 + x4 <= 5*(1-y1) + 200*y1; > x2 >= 3; > x3+x4 >= 3; > x2 <= 3*y2 + 100*(1-y2); > x3+x4 <= 3*(1-y2) + 200*y2; > @BIN(y1); > @BIN(y2); > > The solution is: > Global optimal solution found. > Objective value: 10.00000 > Objective bound: 10.00000 > Infeasibilities: 0.000000 > Extended solver steps: 0 > Total solver iterations: 0 > > Variable Value Reduced Cost > X1 2.000000 0.000000 > X2 3.000000 0.000000 > X3 0.000000 0.000000 > X4 5.000000 0.000000 > Y1 1.000000 0.000000 > Y2 1.000000 0.000000 > > So: x1 = 2, x2 = 3, x3 = 0 and x4 = 5. > > If a good mixed-integer programming code fails to find a feasible > solution, that would mean that the original problem is infeasible. > > R.G. Vickson Another question: If some MIN operations have more than two variables, how could I convert them into MIP equations? For example: MIN{x1, x2} = 5 MIN{x2, x3, x4} = 3 Is the following equations right for the second MIN operation? x2 <= 3ab + 200(1-a) + 200(1-b) x3 <= 3(1-a)b + 200a + 200(1-b) x4 <= 3a(1-b) + 200(1-a) + 200b @BIN(a) @BIN(b) Xu |