cplex: lowering the effective tolerance of cplexlp by scaling the linear program

Question

I'm using cplex linear programming in matlab (cplexlp) to solve the problem

min f'u s.t. Au>=b, u>=lb

using

[u,minima,flag] = cplexlp(f,-A,-b,[],[],lb);

but I need a solution tolerance of below 1e-9, which is the minimal tolerance in documentation. I figured I can just scale the problem (e.g. by 10000) and achieve an effective tolerance of 1e-13.

scale=10000;
tolerance=1e-9;
options = cplexoptimset('cplex');
options.simplex.tolerances.feasibility = tolerance;
options.simplex.tolerances.optimality = tolerance;
[u,minima,flag] = cplexlp(scale*f,-scale*A,-scale*b,[],[],scale*lb,[], [], options);
minima = minima / scale;

It does not work, and the tolerance is improved to 1e-11 but not less. The image below show in log10 scale the 'real solution' (found using a different method) and the solution returned by the algorithm for different parameters (each color is different A,b and the x axes is some parameter of the problem which control the solution). As you can see, the real solution is achieved as long as it is above 1e-11.

Any suggestion for why is it so or how to avoid this problem?

Answer 1

CPLEX, like most other codes, uses double precision arithmetic. Within this environment you usually can trust your results only up to the first 9 or 10, maybe 11, digits. That's also the reason why you cannot set a smaller tolerance in CPLEX.

To get more accurate results you would have to use a solver that uses rational arithmetic. QSopt_ex and SoPlex (with iterative refinement) are two possibilities. I do not know how this is possible from within Matlab.