Message Boards Message Boards

Work with LinearProgramming with very small and very big numbers?

GROUPS:

Hello.

I am solving an lp problem with Mathematica. It works as expected for small size instances but I need to go bigger.

Unfortunately, for bigger instances there are very small numbers (like 10^(-200)) and very big numbers (like 10^50) appearing as coefficients. The LinearProgramming function provides me with solutions (no warnings) for all sizes but the solution vector (x variables) contains negative values from a certain size, although it is explicitly stated in my program that they must be greater or equal 0. Those negative numbers start with being very small (like -10^(-20)) but with greater sizes they are like -4000 for example.

I tried solving it with the DualLinearProgramming and it is in agreement with the LinearProgramming solutions up to a certain small size of the problem (where values o x's are not negative in solution provided by the LinearProgramming) and for bigger sizes it says that there is no solution satisfying the constraints.

I tried all of the possible algorithms and generally Simplex works best.

I tried rescaling my problem in many ways to have more reasonable numbers but it didn't help much. It is quite difficult to come up with scaling since there are many sums of binomial coefficients, exponents and their inverses.

It is not the problem of size in terms of the number of variables or equations since there are no more than few hundreds of them.

Could you suggest me some possible ways of dealing with it? I tried increasing the $MaxExtraPrecision to few hundreds but it didn't help. I am very worried that Mathematica gives solutions for the primal problem (with x's not satisfying constraints) whereas claims to have no solutions for bigger instances of the dual for those cases.

Thanks.

POSTED BY: Darek S.
Answer
9 months ago

One possibility would be to use exact values. If instead you work with finite precision, make sure the input is of high precision and contains no machine numbers. And make sure the result likewise is of high precision. Anything else would be an indication that LinearProgramming was using machine arithmetic which is not going to react well to an extreme level of scale differences.

POSTED BY: Daniel Lichtblau
Answer
9 months ago

Group Abstract Group Abstract