14
$\begingroup$

Often times I have this issue. For example, I need to have a non-negative coefficient, say $c_0$, in my optimization problem (otherwise the problem is not convex). Moreover, to obtain this $c_0$ I analytically solve a problem in MATLAB. This analytic solution also satisfies $c_0 \geq 0$ but returns $c_0 = 10^{-5}$ and assumes this is zero. However, the solver I use complains that the problem is not convex, so assumes $c_0 < 0$.

I face many variants of this issue, especially if I re-optimize a problem and do some algebraic operations in between. It is hard to prevent this most of the time. My questions may be too broad, but:

  1. Do you, as OR people, have this issue generally? Is this a famous phenomenon, or is it just me?
  2. Is there a general way to have the same precision between the programming language (say MATLAB), and the solver (say CPLEX)?
Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ Not just you.. Iis there harm to the validity of the model if the small coefficient, such as $10^{-5}$ is set exactly to zero? Generally, you should try to make input numbers either exactly 0, or within a "small" number of orders of magnitude of 1. If the span exceeds half the number oi digits, so 8 orders of magnitude in double precision, you are asking for a trouble, and you may get it even with less. You can try tightening solver feasibility and optimality tolerances. Can adjust slightly infeasible solutions, for instance with respect to bound constraints, to be exactly feasible, etc $\endgroup$
    – Mark L. Stone
    Commented Jun 1, 2019 at 0:49
  • 1
    $\begingroup$ CPLEX is fussy. For instance, if you input a Quadratic matrix for a QP, and it has 1e-16 level roundoff error, CPLEX might reject it as asymmetric. That can be solved by symmetrizimg the matrix as $0.5(Q + Q^T)$. There are ways of making a slightly numerically non-convex QP convex,. for example by adding a small number to the diagonal, or just to negative eigenvalues. It might happen that your inpit matrix is psd, but due to presolve, the adjusted matrix in the solver comes out to not be nuimercally psd. This is the real world of finite precision computing. Interacrtion of tolerances is key. $\endgroup$
    – Mark L. Stone
    Commented Jun 1, 2019 at 1:02
  • 2
    $\begingroup$ No!!!! :) You must NEVER manually round a small value to 0. You’ll make the problem worse because of nearly parallel constraints. $\endgroup$
    – Edward Lam
    Commented Jun 1, 2019 at 6:37
  • $\begingroup$ @Edward Lam it depends on the situation, That's why I asked the question.Often it is exactly the right thing to do. The interplay of the tolerances in the solver and any larger algorithmic framework within which it is called can be critical. So the OP needs to provide more info. $\endgroup$
    – Mark L. Stone
    Commented Jun 1, 2019 at 11:32
  • 1
    $\begingroup$ I was pointing out that very small (other than exactly zero) or large numbers in solvers, or a wide range of magnitudes of numbers can cause havoc for solvers. if a number can be made exactly zero without doing harm, it should. If it can't, then generally there is something not good in the model, and perhaps its scaling. You might be able to tighten tolerances on solvers, but if things are really bad, might need high precision. See for instance web.stanford.edu/group/SOL/talks/14beijingQuadMINOS.pdf for Quad Precision MINOS. In my own higher level algorithms,I adjust raw solver result $\endgroup$
    – Mark L. Stone
    Commented Jun 1, 2019 at 11:54

2 Answers 2

Reset to default
14
$\begingroup$

Numerical stability (computations going sideways) and numerical tolerances are related but not identical. Floating point arithmetic being subject to rounding and truncation errors (unavoidably), every solver will need to treat things that are "nearly nonnegative", "nearly zero" or "nearly integer" as if they are in fact nonnegative / zero / integer. That includes things like claiming a function is nonnegative if a coefficient has the wrong sign (and is not within tolerance of zero).

CPLEX has tolerance settings for constraint satisfaction, integrality and convergence. I don't know if there is a tolerance setting for the convexity check, but if you poke through the parameters manual you may find one.

It's also relevant whether you are using the MATLAB API for CPLEX (preferable) or exporting a file from MATLAB and reading it into CPLEX (less accurate, especially if you use a LP file as opposed to a SAV file). I've seen a number of cases reported where passing a model via an LP format file produced different results (different solution, numerical errors, ...) from passing the exact same model via SAV format. LP format is text, which produces truncation errors in both directions (reading, writing) that SAV format (which is binary) avoids.

Trust me, you're not alone in this.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I am using MATLAB API. CPLEX was actually just one example, I have this with MOSEK all the time as well. Therefore, I was curious to hear more about people's opinions. Thank you very much about your answer. $\endgroup$
    – independentvariable
    Commented Jun 1, 2019 at 16:35
6
$\begingroup$

(1) Numerical stability is a real issue but not so common in my area of discrete optimisation (for obvious reasons). I only get it in two cases. Sometimes I get preprocessed data that has been rounded, resulting in nearly parallel constraints. Other times I badly implement an iterative algorithm like Benders decomposition, which produces more numerical error in each iteration.

(2) I don’t use MATLAB but I would expect it to use double 64-bit precision in outputs and perhaps calculate using 80-bit precision. You can look into bignum libraries that implement infinite precision in software.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Many thanks! So good to hear about your experiences $\endgroup$
    – independentvariable
    Commented Jun 1, 2019 at 10:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.