Documentation

Filter Content By
Version
Languages
${sidebar_list_label} - Back
${item.name}
next up previous
Next: Dealing with big-M constraints Up: Tolerances and user-scaling Previous: Advanced user scaling

Avoid hiding large coefficients

As we said before, a typical recommendation for improving numerics is to limit the range of constraint matrix coefficients. The rationale behind this guideline is that terms to be added in a linear expression should be of comparable magnitudes so that rounding errors are minimized. For example:

<span>$</span>\begin{array}{rcl} x - 10^{6} y &\geq& 0 \ y&\in&[0,10] \end{array}<span>$</span>
is usually considered a potential source of numerical instabilities due to the wide range of the coefficients in the constraint. However, it is easy to implement a simple (but useless) alternative:
<span>$</span>\begin{array}{rcl} x - 10 y_1 &\geq& 0\ y_1 - 10 y_2 &=& 0\ y_2 - 10 y_3 &=... ...y_4 &=& 0\ y_4 - 10 y_5 &=& 0\ y_5 - 10 y &=& 0\ y&\in&[0,10] \end{array}<span>$</span>
This form certainly has nicer values in the matrix. However, the solution <span>$</span>y=-10^{-6},\ x=-1<span>$</span> might still be considered feasible as the bounds on variables and constraints might be violated within the tolerances. A better alternative is to reformulate
<span>$</span>\begin{array}{rcl} x - 10^{6} y &\geq& 0 \ y&\in&[0,10] \end{array}<span>$</span>
as
<span>$</span>\begin{array}{rcl} x - 10^{3} y' &\geq& 0 \ y'&\in&[0,10^4]\ \end{array}<span>$</span>
where <span>$</span>10^{-3} y' = y<span>$</span>. In this setting, the most negative values for <span>$</span>x<span>$</span> which might be considered feasible would be <span>$</span>-10^{-3}<span>$</span>, and for the original <span>$</span>y<span>$</span> variable it would be <span>$</span>-10^{-9}<span>$</span>, which is a clear improvement over the original situation.

next up previous
Next: Dealing with big-M constraints Up: Tolerances and user-scaling Previous: Advanced user scaling