Detect Numerical Instability with Large-scale optimization problems

Question

We run large-scale optimization problems regularly. They have thousand of variables and tens of thousands of constraints.

Those optimization problems often get numerically instable. In those cases, we fail to pin-point what exactly causes numerical instability (that is a huge pain-point).

We had 2 questions:

1. Is it possible to identify what is causing numerical instability in our optimization problem? [Note: Both theoretical techniques and programmatic tool (preferably python-based) would be helpful]
2. Given a optimization problem, Is it possible to predict deterministically that would it be Numerically instable or not?

Answer 1

Some people at Xpress have worked recently (past couple of years) on automated scaling techniques for LP and MIP, which involves guessing whether a problem will run into numerical issues.

I can point you to this preprint, wherein the authors use the concept of attention level:

The attention level is a measure between 0 and 1 that aims at estimating how likely numerical errors are to occur during an LP or MIP solve

Answer 2

You can take a look at this article/web-page by Gurobi. It specifies some guidelines to identify & correct some numerical issues in models.

Answer 3

In general, I think it is difficult if not impossible to look at a model and say, prior to any computations, that it is going to be unstable ... with one exception. If the largest and smallest absolute values of nonzero constraint coefficients differ by too many orders of magnitude, then you are living dangerously. The model might still be stable, but a wide range of coefficient magnitudes raises the likelihood of instability. Looking at the objective coefficients, I don't know that a wide range of magnitudes would signal likely instability in the sense of basis matrices having large condition numbers, but it could signal potential rounding problems that might lead to suboptimal solutions.

Some solvers provide an easy means to inspect the range of magnitudes.

Answer 4

About the causes: a) Too high or too low values in your matrix, a good rule of thumb is that the ratio of the higgest / lowest coefficient should be lower than 10^6. Take special care with big M's. If the coefficients are needed you can scale the constraint. b) Sometimes constraints that means almost the same thing for example a bound in each node of a graph an a bound in the sum of the nodes, can lead to a close to singular matrix.