# Preconditioning linear program

I have a linear program $$\text{minimize } c^T x \text{ subject to } Ax \geq b$$ where $A$ is of the form $$A = \begin{pmatrix} A_1 \\ A_2 \end{pmatrix}$$ with $A_1$ well-conditioned and $A_2$ well-conditioned up to a positive diagonal scaling from the right, i.e. there is a diagonal matrix $D$ with nonnegative entries such that $A_2 \, D$ is well-conditioned.

When I plug the above original formulation into an LP solver (GLPK), I get an error message about some matrix being singular, so I assume I somehow have to fix the conditioning of the constraint matrix. Is there an efficient way to do this?

• I would try a different LP solver. Many LP solvers are able to deal with these kind of situations. – Erwin Kalvelagen Jul 3 '18 at 9:19

You could just scale $(A_2, b_2)$. However, typically LP solvers will scale and presolve LP models. This may largely undo your own scaling. Also for Simplex methods, the condition of $A_2$ is less important than the condition of the basis matrix $B$.