Is there some methods to solve equations with MIN operation?
in [Math]
|
Prev: 6.- Conjecture .
Next: Name for matrix
From: Ray Vickson on 3 Aug 2010 21:20 On Aug 2, 2:52 am, Torsten Hennig <Torsten.Hen...(a)umsicht.fhg.de> wrote: > > > On Jul 29, 6:55 pm, RayVickson > > <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, RayVickson > > > <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 > > > min: x1 + x2 + x3 + x4 > > s.t. > > x1 >= 5 > > x2 >= 5 > > x2 >= 3 > > x3 >= 3 > > x4 >= 3 > > > Best wishes > > Torsten. > > Or - if the expressions inside the min-operator > become more complicated - make use of the fact > that min(x1,x2,x3) = min(x1,min(x2,x3)), > introduce two new varables x4 and x5, set > x4 = min(x2,x3) > x5 = min(x1,x4) > and convert this with binary variables to a > MILP in the usual way. This won't work---unless we can deal with _nonlinear_ mixed integer problems. If we set min(x2,x3) = x4 and use a binary variable, we have x2 >= x4, x3 >= x4, x2 <= y*x4 + (1-y)*U, x3 <= (1-y)*x4 + y*U, so we have the nonlinear terms y*x4 and (1-y)*x4. R.G. Vickson > > Best wishes > Torsten.
From: Torsten Hennig on 3 Aug 2010 22:39
> On Aug 2, 2:52 am, Torsten Hennig > <Torsten.Hen...(a)umsicht.fhg.de> > wrote: > > > > On Jul 29, 6:55 pm, RayVickson > > > <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, RayVickson > > > > <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 > > > > > min: x1 + x2 + x3 + x4 > > > s.t. > > > x1 >= 5 > > > x2 >= 5 > > > x2 >= 3 > > > x3 >= 3 > > > x4 >= 3 > > > > > Best wishes > > > Torsten. > > > > Or - if the expressions inside the min-operator > > become more complicated - make use of the fact > > that min(x1,x2,x3) = min(x1,min(x2,x3)), > > introduce two new varables x4 and x5, set > > x4 = min(x2,x3) > > x5 = min(x1,x4) > > and convert this with binary variables to a > > MILP in the usual way. > > This won't work---unless we can deal with _nonlinear_ > mixed integer > problems. If we set min(x2,x3) = x4 and use a binary > variable, we have > x2 >= x4, x3 >= x4, x2 <= y*x4 + (1-y)*U, x3 <= > (1-y)*x4 + y*U, so we > have the nonlinear terms y*x4 and (1-y)*x4. > > R.G. Vickson > If we have min(x1,x2,x3) = a, we can introduce a new variable z1 = min(x2,x3). So the equivalent system is min(x1,z1) = a min(x2,x3) = z1. Transforming both equations seperately with binary variables y1, y2 gives x1 >= a z1 >= a x1-a-U*(1-y1) <= 0 z1-a-U*y1 <= 0 x2>= z1 x3>= z1 x2-z1-U*(1-y2) <= 0 x3-z1-U*y2 <= 0. Best wishes Torsten. > > > > Best wishes > > Torsten. > |