0
$\begingroup$

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?

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

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.