Is there some methods to solve equations with MIN operation?
in [Math]
|
Prev: 6.- Conjecture .
Next: Name for matrix
From: Xu Wang on 28 Jul 2010 13:19 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
From: Dann Corbit on 28 Jul 2010 14:25 In article <f1ae43e8-6521-4a0e-b442- bde6545a368a(a)l14g2000yql.googlegroups.com>, wangxu.name(a)gmail.com says... > > 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? The easiest way to solve this sort of thing is with a program, assuming that you have a comparison operator for the data types in your list. For example, here is a C++ program that finds the minimum and maximum of items in a list: #include <cstdlib> template <typename e_type> void minmax(e_type * array, size_t arr_size, e_type * min_e, e_type * max_e) { e_type min_e_type; e_type max_e_type; size_t index, next; if (arr_size % 2) { min_e_type = array[0]; max_e_type = array[0]; next = 1; } else { if (array[0] > array[1]) { max_e_type = array[0]; min_e_type = array[1]; } else { min_e_type = array[0]; max_e_type = array[1]; } next = 2; } for (index = next; index < arr_size; index += 2) { if (array[index] > array[index + 1]) { max_e_type = max_e_type > array[index] ? max_e_type : array [index]; min_e_type = min_e_type < array[index + 1] ? min_e_type : array[index + 1]; } else { max_e_type = max_e_type > array[index + 1] ? max_e_type : array[index + 1]; min_e_type = min_e_type < array[index] ? min_e_type : array [index]; } } *min_e = min_e_type; *max_e = max_e_type; } #ifdef UNIT_TEST #include <cstdio> char string[32767]; double foo[32767]; int main(void) { size_t index = 0; double dmin, dmax; while (fgets(string, sizeof string, stdin)) { foo[index++] = atof(string); if (index > 32766) break; } minmax(foo, index, &dmin, &dmax); printf("min=%f, max=%f\n", dmin, dmax); return 0; } #endif /* c:\dcorbit64\tmp>minmax 1 2 3 4 5 6 7 8 9 10 22 11 32 55 -3 2 11 7 ^Z min=-3.000000, max=55.000000 */
From: Ray Vickson on 28 Jul 2010 19:38 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
From: Xu Wang on 29 Jul 2010 05:32 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
From: Xu Wang on 29 Jul 2010 05:48
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 |