Long time ago my brother and I wrote a paper about presolve in linear programming. A subject that keeps on surprising me. Here is something to think about.
We defined two rows of A to be duplicate if they were identical up to a nonzero multiplier. Hence,
1e-06 x1 -1e-06 x2 >= 0
x1 - x2 <= 0
are duplicate. Normaly the presolve would merge two such constraints too
1e-06 x1 -1e-06 x2 = 0 (1)
or
x1 - x2 = 0 (2)
Oberseve that (x1,x2)=(0.1 , 0) is infeasible for the orginal system but feasible for (1) given a feasibility tolerence of 1.0e-7. Moreover, (x1,x2)=(0 , 0.1) is feasible for the orginal system but infeasible for (2).
Mathematically (1) and (2) are equivalent to the original system. However, in a finite presiscion and using feasibility tolerances they are very different.
The first lesson to be learned is that scaling matters. The second lesson is that we should be careful when we merge duplicate constraints. My preference would be to include the constraint (2) in the presolved problem.
