Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.
