Is there some methods to solve equations with MIN operation?
Xu Wang
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
Dann Corbit
bde654...@l14g2000yql.googlegroups.com>, wangx...@gmail.com
says...
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
*/
Xu Wang
> On Jul 28, 10:19 am, Xu Wang <wangxu.n...@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
>
> (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?
>
>
> > 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
Xu Wang
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
Torsten Hennig
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.
Ray Vickson
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
Ray Vickson
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
Rob Pratt
"Xu Wang" <wangx...@gmail.com> wrote in message
news:55fd3ca6-30d3-40f5...@s9g2000yqd.googlegroups.com...
as
the answer is
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).
Xu Wang
> "Xu Wang" <wangxu.n...@gmail.com> wrote in message
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
Torsten Hennig
> wrote:
> > "Xu Wang" <wangxu.n...@gmail.com> wrote in message
> >
> >
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.
Xu Wang
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
Ray Vickson
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
Xu Wang
> On Jul 29, 2:32 am, Xu Wang <wangxu.n...@gmail.com> wrote:
>
>
>
> > On Jul 29, 1:38 am, Ray Vickson <RGVick...@shaw.ca> wrote:
>
> > > On Jul 28, 10:19 am, Xu Wang <wangxu.n...@gmail.com> wrote:
>
> > > > Hi everyone,
>
> > > > I have to solve a set of equations withMINoperation.
>
> > > >MINoperation:
> > > > among x1 to xn.
>
> > > > A set of equations withMINoperationis like:
> > 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_
> 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.
>
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
Torsten Hennig
min: x1 + x2 + x3 + x4
s.t.
x1 >= 5
x2 >= 5
x2 >= 3
x3 >= 3
x4 >= 3
Best wishes
Torsten.
Torsten Hennig
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.
Ray Vickson
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
Ray Vickson
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
Rock Brentwood
>
> MIN{x1, x2} = b
> MIN{x3, x4} = c
> MIN{x2+x3, x5} = d
> .....
>
> 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.
Ray Vickson
wrote:
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.
Torsten Hennig
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.
>