Is there some methods to solve equations with MIN operation?
in [Math]
|
Prev: 6.- Conjecture .
Next: Name for matrix
From: Torsten Hennig on 2 Aug 2010 01:29 > 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 min: x1 + x2 + x3 + x4 s.t. x1 >= 5 x2 >= 5 x2 >= 3 x3 >= 3 x4 >= 3 Best wishes Torsten.
From: Torsten Hennig on 2 Aug 2010 01:52 > > 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 > > 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. Best wishes Torsten.
From: Ray Vickson on 2 Aug 2010 12:27 On Aug 2, 1:54 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 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) NO, NO, NO! This is _nonlinear_, as it contains the product a*b. If you had computer codes available to solve nonlinear mixed-integer problems, you might be able to use them, but as far as I know they are still in a state of "infancy" and are not yet well-developed. > x3 <= 3(1-a)b + 200a + 200(1-b) > x4 <= 3a(1-b) + 200(1-a) + 200b > @BIN(a) > @BIN(b) > > Xu When we used a single binary variable for min{x1,x2}, that was because we _really_ had two binary variables y1 and y2 but with y1 + y2 = 1 (so we could take y2 = 1-y1). If you have min{x2,x3,x4} you need three binary variables y2,y3,y4 with y2+y3+y4=1. So, we have: x2 >= 3, x3 >= 3, x4 >= 3, x2 <= 3*y2 + U*(y3+y4), x3 <= 3*y3 + U*(y2+y4), x4 <= 3*y4 + U*(y2+y3), y2 + y3 + y4 = 1 and y2, y3, y4 binary. R.G. Vickson
From: Ray Vickson on 2 Aug 2010 16:54 On Aug 2, 9:27 am, Ray Vickson <RGVick...(a)shaw.ca> wrote: > On Aug 2, 1:54 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 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) > > NO, NO, NO! This is _nonlinear_, as it contains the product a*b. If > you had computer codes available to solve nonlinear mixed-integer > problems, you might be able to use them, but as far as I know they are > still in a state of "infancy" and are not yet well-developed. > > > x3 <= 3(1-a)b + 200a + 200(1-b) > > x4 <= 3a(1-b) + 200(1-a) + 200b > > @BIN(a) > > @BIN(b) > > > Xu > > When we used a single binary variable for min{x1,x2}, that was because > we _really_ had two binary variables y1 and y2 but with y1 + y2 = 1 > (so we could take y2 = 1-y1). If you have min{x2,x3,x4} you need three > binary variables y2,y3,y4 with y2+y3+y4=1. So, we have: > x2 >= 3, x3 >= 3, x4 >= 3, x2 <= 3*y2 + U*(y3+y4), x3 <= 3*y3 + > U*(y2+y4), x4 <= 3*y4 + U*(y2+y3), y2 + y3 + y4 = 1 and y2, y3, y4 > binary. Of course, we could write, instead, x2 <= 3*y2 + U*(1-y2), etc., because of the constraint sum (y_j) = 1. As Torsten Hennig points out, if all you have are simple x_j inside the min{...} operations, you can write a simple linear program. Where you need binary variables is in cases having things like sum_j a_{ij} *x_j inside the min{...} (or max{...}). R.G. Vickson > > R.G. Vickson
From: Rock Brentwood on 3 Aug 2010 19:16
On Jul 28, 12:19 pm, Xu Wang <wangxu.n...(a)gmail.com> wrote: > Hi everyone, > > A set of equations with MIN operation is like: > > MIN{x1, x2} = b > MIN{x3, x4} = c > MIN{x2+x3, x5} = d > ..... > > Could anyone give me a hint about which part of mathematics does this > problem belong to? This is the tropical semiring -- the (min, +) semiring. The + operation plays the role of the product, while the min operation plays the role of the sum. Addition in this semiring is idempotent, since min(a,a) = a. One also generally adds in an infinity, W, setting min(x,W) = W = min(W,x) and W+x = W = x+W. The roles of the sum and product can be made more transparent by writing this in exponential form. Then the equations become A^{x1} + A^{x2} = A^b, A^{x3} + A^{x4} = A^c and A^{x2} A^{x3} = A^d. Then arithmetic + operation actually becomes a product, while the min operation becomes an idempotent addition operator + in the semiring. The role of infinity is then played by 0. Idempotent semirings are also called dioids. Idempotency (1998) edited by Gunawaradena is a comprehensive treatment of dioids and quantales. The tropical dioid can then be defined as the set of all exponents A^r (for non-negative reals r), plus 0, subject to the axioms 0 < A^r and A^r < A^s when r > s. The semiring + is your min and one has A^r + A^s = A^{min(r,s)}, 0 + A^r = A^r = A^r + 0. Tropical semirings are closely associated with "shortest paths" type algorithms. |