1
$\begingroup$

For solving a very sparse LP: {min $cx$: s.t.: $A_{m \times n}x=b$ , $x\geq 0$}, which one of the following algorithms is faster?

  1. Logarithmic barrier method
  2. Other variants of the interior point method
  3. Simplex method

What is the best worst case complexity? In general, which algorithm performs well in practice for sparse matrices?

Improve this question
$\endgroup$
1
  • $\begingroup$ ArnoldNeumaier has a good point... Is there any structure in your matrix's sparsity pattern? $\endgroup$
    – Paul ♦
    Jul 25 '12 at 20:02
2
$\begingroup$

The speed of all three methods (which are in fact generic patterns for algorithms rather than algorithms) depends a lot on who implemented which details. A sensible implementation of each method can be far better than a poor implementation of any of the others.

The complexity in the sparse case depends a lot on the sparsity pattern, and there are no results on the general sparse case.

Improve this answer
$\endgroup$
1
  • $\begingroup$ A comparison of large-scale LP solvers can be found at here. In particular, comparison between state of the art simplex and barrier implementations see this. $\endgroup$
    – Ali
    Jul 26 '12 at 15:15

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.