LPSolve (linear programming solver) error?

Posted on 2008-07-21 23:15 By qzy888 (4)

Categories:

Math Advice (Student)

Hi,

I've written a simple LPSolve test program. But it seems to fail to give me the correct answer that satisfy the constraints. Here is the code:

with(Optimization):

cnsts := {x1 + x2 + x3 + x4 + x5 >= 1, x1+x2+x3+x11+x6 >= 1, x7+x9+x10+x4+x5 >=1, x7+x9+x10+x4+x5 >= 1, x7+x9+x10+x11+x6 >=1, x8 + x9 + x10+x4+x5 >=1, x8+x9+x10+x11+x6 >=1};

obj := x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11;

LPSolve(obj,cnsts,assume = {nonnegative});

The answer I get is:

[1.9999999989674, [x1 = 0., x2 = 0.99999999896740222, x11 = 0., x6 = 0., x7 = 0., x9 = 0.99999999896740222, x10 = 0., x8 = 0., x3 = 0., x4 = 1.03259778874000004 *10^(-9) , x5 = 0.]]
which doesn't staisfy the 2nd, 5th and last constraints.

Could you please try and verify this? Thanks a lot!

Rounding

Comment on 2008-07-21 23:45 from alec ( Maple Rating 4

1608)

As usual in such cases, the answers should be rounded, and after that will satisfy the constraints.

Alec

Rounding based on what?

Comment on 2008-07-21 23:54 from qzy888 (4)

Thanks for the reply. I also suspect that Maple somehow rounded each value of the constraint so that it is satisified. Apparently it has its certain precision for rounding. But I would say it is not correct for my application. Is there any way I can get around this to get the accurate answer?

Double the number of digits

Comment on 2008-07-22 00:04 from alec ( Maple Rating 4

1608)

Set twice as many digits as necessary and then round to half of them. That usually good enough.

Alec

feasibility tolerance

Comment on 2008-07-26 11:49 from acer ( Maple Rating 4

1410)

Have a look at the help-page ?Optimization,Options and search for the feasibilitytolerance option. It can be used to pass a specific value of the allowed violation in the constraints.

> restart:

> with(Optimization):

> cnsts := {x1+x2+x3+x4+x5 >= 1,
>  x1+x2+x3+x11+x6 >= 1, x7+x9+x10+x4+x5>=1,
>  x7+x9+x10+x4+x5 >= 1, x7+x9+x10+x11+x6 >=1,
>  x8+x9+x10+x4+x5 >=1, x8+x9+x10+x11+x6 >=1}:

> obj := x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11:

> sol := LPSolve(obj,cnsts,assume={nonnegative}):

> eval(convert(cnsts,list),sol[2]);
[1 <= 1.000000000, 1 <= 0.9999999990, 1 <= 1.000000000, 1 <= 0.9999999990,
 
    1 <= 1.000000000, 1 <= 0.9999999990]
 
> sol2 := LPSolve(obj,cnsts,assume={nonnegative},
>                 feasibilitytolerance=0.1e-13):

> eval(convert(cnsts,list),sol2[2]);
[1 <= 1.000000000, 1 <= 1.000000000, 1 <= 1.000000000, 1 <= 1.000000000,
 
    1 <= 1.000000000, 1 <= 1.000000000]

I suppose that it might not always make sense to set that tolerance very small without also increasing the working precision.

You can also set infolevel[Optimization]:=3 and see which value gets used for that tolerance, even when you don't specify it yourself as an optional argument.

acer