Is there some methods to solve equations with MIN operation?
in [Math]
|
Prev: 6.- Conjecture .
Next: Name for matrix
From: Torsten Hennig on 29 Jul 2010 03:02 > On Jul 28, 7:19 pm, 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 > > ..... > > > > 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 got a method. It is to solve the following > equations. > > MIN(x1, x2) = (x1+x2-|x1-x2|)/2 = b > ... > x1 >= b > x2 >= b > ... > > Is there some ways to solve these equations? > > Thank you. > > Xu > min(x,y) = a can either be rewritten as x = a y >= a or as x >= a y = a. So you could solve two LP's and see which one yields a feasible solution. If the number of min-operators is n, this method gives 2^n LPs to be solved - so only use it if n is small. Best wishes Torsten.
From: Ray Vickson on 29 Jul 2010 12:55 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
From: Ray Vickson on 29 Jul 2010 14:11 On Jul 29, 2:48 am, Xu Wang <wangxu.n...(a)gmail.com> wrote: > On Jul 28, 7:19 pm, 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 > > ..... > > > 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 got a method. It is to solve the following equations. > > MIN(x1, x2) = (x1+x2-|x1-x2|)/2 = b > ... > x1 >= b > x2 >= b > ... > > Is there some ways to solve these equations? It depends on the objective of the original problem. Handling absolute values in optimization can be done using linear programming for SOME limited, special cases, but in general it requires the presence of binary variables. We can write z1 - z2 = x1 - x2, with z1 >= 0 and z2 >= 0. Then we can represent |x1 - x2| as z1 + z2 --- provided that just *one* of the z_i is > 0. For example, consider z1 - z2 = -5, z1, z2 >=0. We have |-5| = 5 = z1 + z2 IF we have z1 = 0 we have -z2 = -5, so z2 = 5 and z1 + z2 = 5. If we are minimizing something like +|x1 - x2| we can just write min (z1 + z2), which would be an ordinary linear program. It works because among all the combinations of non-negative z1, z2 having z1 - z2 = -5, the one with z1 = 0 and z2 = 5 minimizes the sum z1 + z2. However, this won't work if we are maximizing something like |x1 - x2|, or if we have |x1 - x2| in a constraint equation or inequality, because then both z1 and z2 might want to be > 0. So, in such a case we need an additional constraint: "either z1 = 0 or z2 = 0". If we nave a known upper bound U on |x1 - x2| we can handle this by a binary variable and some constraints: z1 - z2 = x1 - x2, z1 <= y*U, z2 <= (1-y)*U, z1,z2 >= 0, y binary. Note that if y = 0 this gives 0 <= z1 <=0 (hence z1 = 0) and 0 <= z2 <= U. Since z1 - z2 = x1 - x2 and z1 = 0, we have z2 = x2 - x1 and |x1 - x2| = x2 - x1. If y = 1 we have 0 <= z1 <= U, 0 <= z2 <= 0 (so z2 = 0) and z1 - z2 = x1 - x2. Thus, z1 = |x1 - x2| = x1 - x2. Basically, absolute values and max or min operations can be handled very similarly. R.G. Vickson > > Thank you. > > Xu
From: Ray Vickson on 29 Jul 2010 14:20 On Jul 29, 2:48 am, Xu Wang <wangxu.n...(a)gmail.com> wrote: > On Jul 28, 7:19 pm, 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 > > ..... > > > 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 got a method. It is to solve the following equations. > > MIN(x1, x2) = (x1+x2-|x1-x2|)/2 = b > ... > x1 >= b > x2 >= b > ... > > Is there some ways to solve these equations? It depends on the objective of the original problem. Handling absolute values in optimization can be done using linear programming for SOME limited, special cases, but in general it requires the presence of binary variables. We can write z1 - z2 = x1 - x2, with z1 >= 0 and z2 >= 0. Then we can represent |x1 - x2| as z1 + z2 --- provided that just *one* of the z_i is > 0. For example, consider z1 - z2 = -5, z1, z2 >=0. We have |-5| = 5 = z1 + z2. IF we have z1 = 0 we have -z2 = -5, so z2 = 5 and z1 + z2 = 5. If we are minimizing something like +|x1 - x2| we can just write min (z1 + z2), which would be an ordinary linear program. It works because among all the combinations of non-negative z1, z2 having z1 - z2 = -5, the one with z1 = 0 and z2 = 5 minimizes the sum z1 + z2. However, this won't work if we are *maximizing* something like |x1 - x2|, or if we have |x1 - x2| in a constraint equation or inequality, because then both z1 and z2 might want to be > 0. So, in such a case we need an additional constraint: "either z1 = 0 or z2 = 0". If we have a known upper bound U on |x1 - x2| we can handle this by a binary variable and some additional constraints: z1 - z2 = x1 - x2, z1 <= y*U, z2 <= (1-y)*U, z1,z2 >= 0, y binary. Note that if y = 0 we get 0 <= z1 <=0 (hence z1 = 0) and 0 <= z2 <= U. Since z1 - z2 = x1 - x2 and z1 = 0, we have z2 = x2 - x1 and | x1 - x2| = x2 - x1. If y = 1 we have 0 <= z1 <= U, 0 <= z2 <= 0 (so z2 = 0) and z1 - z2 = x1 - x2. Thus, z1 = |x1 - x2| = x1 - x2. Basically, absolute values and max or min operations can be handled very similarly. Just incorporate the above constraints and put z1 + z2 wherever you see |x1 - x2|. R.G. Vickson > > Thank you. > > Xu
From: Rob Pratt on 29 Jul 2010 14:48
"Xu Wang" <wangxu.name(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). |