MathGroup Archive 2003

[Date Index] [Thread Index] [Author Index]

Search the Archive

Another problem with ConstrainedMin

  • To: mathgroup at smc.vnet.net
  • Subject: [mg40153] Another problem with ConstrainedMin
  • From: Uri Zwick <zwick at tau.ac.il>
  • Date: Sun, 23 Mar 2003 04:12:19 -0500 (EST)
  • Sender: owner-wri-mathgroup at wolfram.com

Hi,

I am encountering another problem with ConstrainedMin.
(For the previous one, see my previous posting from February 26.)
This time it is a serious numerical problem that occurs under
Mathematica 4.2 for Windows but not under Mathematica 4.1 for 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}

I try to minimize x+y under these constraints.
The result I get is a complete nonsense:

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 of the problem.

Using Mathematica 4.1 for LINUX I get the (hopefully) correct result:

Out[2] = {50.1946934554904018455090408679`16.699,
     {x -> 49.1946934554904053982227196684`17, y -> 1.`17}}

Did anyone encounter similar problems with ConstrainedMin?
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             |
---------------------------------------------------------------------




  • Prev by Date: Re: Finite Fields and Polynomials
  • Next by Date: Plot a recurrence relation
  • Previous by thread: A numerical problem with ConstrainedMin
  • Next by thread: Re: Another problem with ConstrainedMin