Try our new documentation site (beta).

The case of linear systems:

Solving linear systems is a very common sub-routine in any MI(QC)P-solver, as we have to solve many linear systems during the full execution of the algorithm.

So, consider that we have a linear system <span>$</span>A x = b<span>$</span> with an unique solution (i.e. <span>$</span>A<span>$</span> is a square matrix with full rank), and you want to evaluate how the solution to the system might change if we perturb the right-hand side <span>$</span>b<span>$</span>. Since the system has a unique solution, we know that given <span>$</span>b<span>$</span>, the solution will be <span>$</span>A^{-1}b<span>$</span>, and if we perturb <span>$</span>b<span>$</span> with <span>$</span>\varepsilon<span>$</span>, the solution will be <span>$</span>A^{-1}(b+\varepsilon)<span>$</span>. A measure for the relative change in the solution with respect to the relative change in the input would be the ratio

<span>$</span>\eta(b,\varepsilon):=\frac{\Vert A^{-1}b\Vert}{\Vert A^{-1}(b+\varepsilon)\Vert}/\frac{\Vert b\Vert}{\Vert b+\varepsilon\Vert}.<span>$</span>
Note that the above definition is independent of the magnitudes of <span>$</span>b<span>$</span> and <span>$</span>\varepsilon<span>$</span>. From there, the worst possible ratio would be the result of
<span>$</span>\kappa(A):=\max_{b,\varepsilon}\eta(b,\varepsilon).<span>$</span>
This quantity is known as the condition number of the matrix <span>$</span>A<span>$</span>. It is not hard to prove that
<span>$</span>\kappa(A)=\frac{\lambda_{\max}}{\lambda_{\min}},<span>$</span>
where <span>$</span>\lambda_{\max}<span>$</span> and <span>$</span>\lambda_{\min}<span>$</span> are the maximum and minimum, respectively, eigenvalues of <span>$</span>A<span>$</span>. Equivalently
<span>$</span>\kappa(A)=\frac{\Vert A\Vert}{\Vert A^{-1}\Vert}.<span>$</span>
A common interpretation of <span>$</span>\kappa(A)=10^k<span>$</span> is that, when solving the system <span>$</span>A x = b<span>$</span>, you may lose up to <span>$</span>k<span>$</span> digits of accuracy in <span>$</span>x<span>$</span> from the accuracy you have in <span>$</span>b<span>$</span>.

The condition number for the optimal simplex basis in an LP is captured in the KappaExact attribute. A very large <span>$</span>\kappa<span>$</span> value might be an indication that the result might be unstable.

When this is indeed the case, the best advice is to scale the constraint matrix coefficients so that the resulting range of coefficients is small. This transformation will typically reduce the <span>$</span>\kappa<span>$</span> value of the final basis; please refer to the Scaling section for a discussion on how to perform this rescaling, and also for caveats on scaling in general.

Try Gurobi for Free

Choose the evaluation license that fits you best, and start working with our Expert Team for technical guidance and support.

Evaluation License
Get a free, full-featured license of the Gurobi Optimizer to experience the performance, support, benchmarking and tuning services we provide as part of our product offering.
Academic License
Gurobi supports the teaching and use of optimization within academic institutions. We offer free, full-featured copies of Gurobi for use in class, and for research.
Cloud Trial

Request free trial hours, so you can see how quickly and easily a model can be solved on the cloud.

Search

Gurobi Optimization