Originally posted by: Panos_N89

Hi all! 

Firstly, let me briefly describe my application:

I have modelled an extended electrical power network in MATLAB, where different operational situations are studied. These situations (line or unit outages) correspond to a large constraint matrix, while several technical specifications determine the rhs, upper and lower bounds of the LP problem created. MATLAB calls C Callable Libraries via a MEX file. My interest mainly focuses on getting Presolve Status Information through CPXXgetprestat in order to determine which of the above operational constraints are critical (still present in the Presolved LP).

Originally posted by: T_O

1e-14 is basically nothing. Have a look at the default tolerances that CPLEX uses and at the minimal tolerances that you can set at all.

Typically the best way to get a numerically stable model ist to reformulate it in some way. Maybe you can tell us the maximal and minimal coefficients in your model?

Best regards,
Thomas

Originally posted by: Panos_N89

First of all, thank you for your answer, Thomas.

Well, I had already taken a look at CPLEX tolerances, and I was quite surprised to see CPLEX return different results corresponding to a difference around e-14.
I attach two small LP problems ( one for each of the two different ways constructing the LP as mentioned in my first post) for anyone that would like to have a look:
they have the same lower and upper bounds vectors, while maximum difference in any pair of elements of their constraint matrices or rhs vectors is around e-15! Nevertheless, CPLEX presolve returns slightly different results!

The above fact probably shows that CPLEX is sensitive to such small changes. So, maybe, the mismatch between presolve results and theoretically expected values in my LP is due to precision issues during matrices calculation. This assumption made me use multiprecision computation but still I'm unable to get the deisred results.

Regarding your question, constraint coefficients generally range from -1.5 to 1.5 ( although the majority of them is of values around 0.1), rhs from 0.1 to 2, lb from 0 to 0.33 and ub from 0.035 to 0.55. The fact is that I have already reformulated my model in order to achieve a narrow variation in orders of magnitude of the coefficients. Do you think I should try to further improve it?

 

Originally posted by: T_O

When I look at your model, there are constraints like:

x1 + x3 + x4 + x5 - 5.55111512312578e-17 x6 <= 0.63

So you have 17 orders of magnitude between the coefficients in a constraint. If you need a reliable solution to such a model, I would not trust any floating point solver.

On the other hand, your models seem quite small. I could solve them using exact arithmetic in almost no time.

Again: For floating point numbers, a difference of 1e-14 cannot really be called a difference.

Best regards,
Thomas

Originally posted by: Laci Ladanyi

The problems you try to feed to cplex are extremely badly conditioned.

The fact that the coefficients are between -1.5 and 1.5 means nothing, what matters is the magnitude of the numbers. You have numbers on the order of 1e00 and numbers on the order of 1e-15, and a significant number of both at that. You just simply cannot expect any software using double precision input to work with such numbers. Also, at a cursory glance it seems almost every number is either on the order of 1e-1 to 1e00 or on the order of 1e-16 to 1e-14. In other words, there is a huge gap in precision. Are you *sure* that those tiny numbers are not round-off errors from your previous calculations? Should not they be 0? 

Finally, while it is true that the corresponding entries in LP1 and LP2 are not very different, look at where the differences are! For example:

LP1: c25:  - x1 + 1.33226762955019e-15 x3 - x4 + 3.88578058618805e-16 x5 + 2.22044604925031e-16 x6 <= 0.0300000000000004

LP2: c25:  - x1 - x4 <= 0.0299999999999999

or:

LP1: c31:  x1 + 3.49720252756924e-15 x3 + 4.55191440096314e-15 x4
       + 1.99840144432528e-15 x5 + 6.38378239159465e-16 x6 <= 0.330000000000002
LP2: c31:  x1 + 1.2490009027033e-15 x3 + 1.52655665885959e-15 x4
       + 6.93889390390723e-16 x5 + 3.12250225675825e-16 x6 <= 0.330000000000001

In the first case a jump from 0 to nonzero is bad. In the second case the coefficients are doubled and tripled. So even though the absolute difference is small, the relative difference is huge, and the relative difference matters a lot more in terms of sensitivity than the absolute difference.

I recommend that you take a very serious look at how you generate these instances. First, decide whether those tiny numbers should really be 0. If you must have them, then try to scale the rows or columns so that there is no such big discrepancy in the magnitude of the coefficients. If that is impossible, too, then you can try to use an arbitrary precision solver, though I'm afraid that won't be much use for you either, since a solver is only as good as the data fed in: the exact solver will just amplify the round-off errors you get from your previous computations.

--Laci

Originally posted by: Panos_N89

Wow, I'm really grateful to both of you. Thank you for your detailed answers!

@ Thomas
You are definitely right about the orders of magnitude. I was focusing on the range of coefficients, totally wrong.. The LPs I attached were deliberately small to be easily observed. My actual problem has about a million constraints.

@ Laci
You really opened my eyes. After careful observation, it turned out that all those small numbers should be equal to zero. Now, things are much prettier :) 

Thanks again!