A numerical problem with ConstrainedMin
- To: mathgroup at smc.vnet.net
- Subject: [mg40152] A numerical problem with ConstrainedMin
- From: Uri Zwick <zwick at tau.ac.il>
- Date: Sun, 23 Mar 2003 04:12:16 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
Hi,
I am running into another problem with ConstrainedMin.
(For the first problem, see my previous posting from February 26.)
This time it is a serious numerical problem. It occurs under
Windows, but not under LINUX!
I am solving a relatively simple linear program in only two
variables x,y. There are 48 inequalities, each of the form
a + b*x + c*y >=0 , where a is negative and b and c are positive.
The numbers a,b,c all have a precision of 17.
The inequalities are:
In[1] :=
ineq = {-2.34619140625`17 + 0.080078125`17*x + 0.04443359375`17*y >= 0,
-2.375`17 + 0.125`17*x + 0.0625`17*y >= 0,
-1.6796875`17 + 0.09375`17*x + 0.0703125`17*y >= 0,
-4.9342041015625`17 + 0.14111328125`17*x + 0.0716552734375`17*y >=
0,
-6.408050537109375`17 + 0.1361083984375`17*x +
0.072174072265625`17*y >=
0, -3.9736328125`17 + 0.12890625`17*x + 0.0732421875`17*y >= 0,
-7.364093780517578125`17 + 0.1480865478515625`17*x +
0.079021453857421875`17*y >= 0, -6.0248260498046875`17 +
0.15374755859375`17*x + 0.0811309814453125`17*y >= 0,
-7.32013702392578125`17 + 0.160064697265625`17*x +
0.08586883544921875`17*y >= 0, -6.82013702392578125`17 +
0.160064697265625`17*x + 0.08586883544921875`17*y >= 0,
-5.537353515625`17 + 0.1533203125`17*x + 0.087646484375`17*y >= 0,
-5.037353515625`17 + 0.1533203125`17*x + 0.087646484375`17*y >= 0,
-3.6923828125`17 + 0.16015625`17*x + 0.0888671875`17*y >= 0,
-6.615447998046875`17 + 0.1663818359375`17*x +
0.090606689453125`17*y >=
0, -6.115447998046875`17 + 0.1663818359375`17*x +
0.090606689453125`17*y >= 0, -5.69354248046875`17 +
0.179443359375`17*x + 0.09356689453125`17*y >= 0,
-1.40625`17 + 0.125`17*x + 0.09375`17*y >= 0,
-5.3497314453125`17 + 0.20556640625`17*x + 0.0994873046875`17*y >=
0,
-4.60107421875`17 + 0.177734375`17*x + 0.10205078125`17*y >= 0,
-3.26953125`17 + 0.140625`17*x + 0.10546875`17*y >= 0,
-2.76953125`17 + 0.140625`17*x + 0.10546875`17*y >= 0,
-4.509765625`17 + 0.1953125`17*x + 0.115234375`17*y >= 0,
-4.009765625`17 + 0.1953125`17*x + 0.115234375`17*y >= 0,
-9.4328899383544921875`17 + 0.25582122802734375`17*x +
0.1202716827392578125`17*y >= 0, -3.75`17 + 0.25`17*x +
0.125`17*y >=
0, -2.375`17 + 0.5`17*x + 0.125`17*y >= 0,
-1.375`17 + 0.5`17*x + 0.125`17*y >= 0,
-6.725830078125`17 + 0.2822265625`17*x + 0.125732421875`17*y >= 0,
-5.725830078125`17 + 0.2822265625`17*x + 0.125732421875`17*y >= 0,
-2.859375`17 + 0.1875`17*x + 0.140625`17*y >= 0,
-2.359375`17 + 0.1875`17*x + 0.140625`17*y >= 0,
-4.73046875`17 + 0.359375`17*x + 0.14453125`17*y >= 0,
-3.73046875`17 + 0.359375`17*x + 0.14453125`17*y >= 0,
-10.90069580078125`17 + 0.385009765625`17*x + 0.17547607421875`17*y
>=
0, -9.90069580078125`17 + 0.385009765625`17*x +
0.17547607421875`17*y >= 0, -2.3125`17 + 0.25`17*x + 0.1875`17*y
>= 0,
-1.8125`17 + 0.25`17*x + 0.1875`17*y >= 0,
-8.10546875`17 + 0.484375`17*x + 0.20703125`17*y >= 0,
-7.10546875`17 + 0.484375`17*x + 0.20703125`17*y >= 0,
-14.8677978515625`17 + 0.45556640625`17*x + 0.2113037109375`17*y >=
0,
-13.8677978515625`17 + 0.45556640625`17*x + 0.2113037109375`17*y >=
0,
-4.78125`17 + 0.625`17*x + 0.21875`17*y >= 0,
-3.78125`17 + 0.625`17*x + 0.21875`17*y >= 0,
-17.865779876708984375`17 + 0.5116424560546875`17*x +
0.240543365478515625`17*y >= 0, -1.75`17 + 1.`17*x + 0.25`17*y >=
0,
-10.45166015625`17 + 0.564453125`17*x + 0.25146484375`17*y >= 0,
-6.4609375`17 + 0.71875`17*x + 0.2890625`17*y >= 0,
-0.5`17 + 0.5`17*y >= 0}
When I try to minimize x+y under these constraints, using
Mathematica 4.2 for Windows, I get a nonsense solution:
In[2] := ConstrainedMin[x + y, ineq, {x, y}]
Out[2] := \!\({0``-1.6966, {x \[Rule] 0.`, y \[Rule] 0.`}}\)
Note that the solution { x->0. , y->0. } satisfies NONE of
the constraints!
Using Mathematica 4.1 for LINUX I get the (hopefully) correct solution:
{50.1946934554904018455090408679`16.699,
{x -> 49.1946934554904053982227196684`17, y -> 1.`17}}
Did anyone else encountered similar problems?
In any case, use ConstrainedMin with great caution!
Best regards,
Uri
---------------------------------------------------------------------
| Prof. Uri Zwick | http://www.cs.tau.ac.il/~zwick |
| Dept. of Computer Science | zwick at tau.ac.il |
| Tel Aviv University | |
| Tel Aviv 69978 | PHONE: +972 3 6409610 |
| ISRAEL | FAX: +972 3 6409357 |
---------------------------------------------------------------------