12
$\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?

$\endgroup$
  • 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 '13 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 '13 at 18:40
  • $\begingroup$ I have edited the question to make my interest clearer. $\endgroup$ – shuhalo Jan 22 '13 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 '13 at 4:11
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.

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