How to rescale a linear program before launching it in MOSEK

Question

I want to use MOSEK to check if a linear program (LP) has a solution (I only need to check the feasibility of the LP).

Some coefficients entering the LP are much smaller than others. E.g., some coefficients are of the order 10^(-15), while the others are of the order of 10^(-2).

From reading MOSEK's instructions, it seems preferable to rescale the LP prior to run the optimiser to ensure accuracy.

However, I don't know how to rescale and I would like your advise. For instance, I rescale by multiplying everything, e.g., by 10^(-10), the small coefficients become acceptable, but the others become too large. Also, there is no "unit of measure" associated with the coefficients that I can change.

Question: What can be a correct way of rescaling? If rescaling is not possible, what can I do to ensure accuracy?

This is the LP:

Ax=b
Cx<=d

A and C are the matrices with coefficients of different order of magnitude. A is mxn and D is jxn, with m<n and j<n. A has rank m. D has rank h<j.

Answer 1

No one can tell you what the correct way is to scale your problem. If there was a simple formula for that Mosek would have it build in. This is confirmed by the citation in

https://twitter.com/e_d_andersen/status/1245345927411503104

You should start by asking yourself how many digits in the input data are accurately known. Maybe the answer is 8 and then a number like 10^-15 is random noise from for instance rounding errors and should be truncated to 0.

Next, a piece of good advice is to choose decent units the constraints, and variables. For instance, it is unlikely to be a good idea to use miliseconds and lightyears for units in the model.

In other words by using the knowledge of your model that only you have you should build a well-scaled model. If that is impossible you may have to change your model. Ultimately, if that is not possible either you should use a high-precision (and slow) optimizer that is not available in Mosek.