Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Another problem with ConstrainedMin

• To: mathgroup at smc.vnet.net
• Subject: [mg40161] Re: Another problem with ConstrainedMin
• From: bobhanlon at aol.com (Bob Hanlon)
• Date: Mon, 24 Mar 2003 04:28:29 -0500 (EST)
• References: <b5jtci$mab$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

<< Subject: [mg40161] Another problem with ConstrainedMin
From: Uri Zwick zwick at tau.ac.il 
To: mathgroup at smc.vnet.net

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!

>>

$Version



4.2 for Mac OS X (August 22, 2002)



ConstrainedMin[x+y,ineq,{x,y}]



{0``-1.6966, {x -> 0., y -> 0.}}



You can workaround the problem by using Rationalize



ConstrainedMin[x+y,Rationalize[ineq,0],{x,y}]



{974279/19410, {x -> 954869/19410, y -> 1}}



N[%, 17]



{50.1946934569809376609994836283`17, 
  {x -> 49.1946934569809376609994837644`17, y -> 1.`17}}


Bob Hanlon