1

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?

gTcV
  • 671

1 Answers1

2

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$.

I would try a different LP solver. Note that some solvers will have options to

  • choose a more aggressive scaling method
  • put extra emphasis on numerical precision (at the expense of speed)
  • use quad precision
Erwin Kalvelagen
  • 4,267