13
$\begingroup$

The simplex algorithm is often treated either within real arithmetic, or in the discrete world with exact computations. However, it seems to be implemented most often with floating-point arithmetic.

This leads to the question whether the simplex algorithm should be regarded as a numerical algorithm, in particular how round-off errors affect the computation. I am not interested in practical implementations, but rather in theoretical foundations.

Are you aware of any research on this issue?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ If you are interested in implementations of the simplex algorithm, then I would suggest you to ask the question in or-exchange.com $\endgroup$
    – Snowie
    Jan 22, 2013 at 14:00
  • $\begingroup$ @Snowie: This question is less about practical implementation but rather about theoretical aspects. There has been work in theoretical foundations of numerical analysis, and I wonder whether it has affected the theory of the simplex algorithm. Anyways, thanks for the link still. $\endgroup$
    – shuhalo
    Jan 22, 2013 at 18:40
  • $\begingroup$ I have edited the question to make my interest clearer. $\endgroup$
    – shuhalo
    Jan 22, 2013 at 18:49
  • 3
    $\begingroup$ Have you looked at smoothed analysis? This work not only addresses the average-case running time, but also the average-case stability. $\endgroup$
    – Peter Shor
    Jan 26, 2013 at 4:11

1 Answer 1

Reset to default
3
$\begingroup$

Yes, there is research on this issue.

The Simplex Method is Not Always Well Behaved, Wlodzimierz Ogryczak

retroLP, An Implementation of the Standard Simplex Method, Gavriel Yarmish and Richard Van Slyke

A Numerically Stable Form of the Simplex Algorithm, Philip E. Gill and Walter Murray

You might also be interested in the revised simplex method. This method can take advantage of matrix sparsity; it doesn't keep a representation of the entire matrix. This thesis was of great interest to me: A Comparison of Simplex Method Algorithms.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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