An example of a badly scaled model with an easy fix

A scaled down version of problem we just received at MOSEK is

min s^2
st.   Ax - b = s   (P)
       x >= 0

Assume for simplicity A is a matrix with 1 row. Now in this case the elements in A is very large i.e. of the order of magnitude 10^7.  This implies the problem (P)  is badly scaled because the row contains a lot of elements of the size 10^7 and one of the size 1.

Now an equally good model is


min s^2
st.   Ax - b = (||A||_inf) s   (P')
       x >= 0


which is nicely scaled. An optimal solution to (P') is clearly also optimal to (P)!

Note this line of thinking could be relevant anywhere were penalty variables is employed. Many optimization problems contains penalty variables.

An observation about ns1687037

Hans Mittleman test various optimization software packages on his benchmark website. One of the test  problems is ns1687037. An inspection of that problem reveals many constraint blocks of the form

R0002624: 5.015e+004 C0024008   ....+ C0025749 = 5.0307748e+007
R0002625: 0e+000 <= - C0025749 + C0025750
R0002626: 0e+000 <= C0025749 + C0025750
R0002627: 1.9877659e-008 C0025750 - C0025751 = 0e+000
                  C0025749 is free

These constraints implies

 -C0025750  <=  C0025749 <=  C0025750
1.9877659e-008 C0025750  = C0025751

and hence

1.9877659e-008   abs( C0025749)  <= C0025751

In other words variable C0025749 is an elastic/penalty variable for constraint R0002624. Moreover, we see variable C0025751 is identical 1.0e-8 of the elastic variable in constraint R0002624. Now the right hand side of constraint R0002624 is 10^7 and hence it is more or less the rounding error that is penalized. That makes me wonder if that model provides reliable results or does what the author wants!