<p>Yes, there is research on this issue.</p>

<p><a href="http://www.ia.pw.edu.pl/~wogrycza/publikacje/artykuly/mylinalg.pdf" rel="nofollow">The Simplex Method is Not Always Well Behaved</a>, Wlodzimierz Ogryczak</p>

<p><a href="http://cis.poly.edu/rvslyke/implmnt.pdf" rel="nofollow">retroLP, An Implementation of the Standard Simplex Method</a>, Gavriel Yarmish and Richard Van Slyke</p>

<p><a href="http://www.sciencedirect.com/science/article/pii/0024379573900475" rel="nofollow">A Numerically Stable Form of the Simplex Algorithm</a>, Philip E. Gill and Walter Murray</p>

<p>You might also be interested in the <a href="http://en.wikipedia.org/wiki/Revised_simplex_method" rel="nofollow">revised simplex method</a>.  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 href="http://www.cise.ufl.edu/research/sparse/Morgan/index.htm" rel="nofollow">A Comparison of Simplex Method Algorithms</a>.</p>

CC BY-SA 3.0
2014-06-06T17:54:40.903Z
2014-06-09T18:03:46.933Z
2014-06-09T18:03:46.933Z
jnm2
<p>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.</p>

<p>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.</p>

<p>Are you aware of any research on this issue?</p>

CC BY-SA 3.0
2013-01-22T14:00:20.613Z
If you are interested in implementations of the simplex algorithm, then I would suggest you to ask the question in http://www.or-exchange.com/
Snowie
CC BY-SA 3.0
2013-01-22T18:40:26.137Z
@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.
shuhalo
CC BY-SA 3.0
2013-01-22T18:49:52.827Z
I have edited the question to make my interest clearer.
shuhalo
CC BY-SA 3.0
2013-01-26T04:11:07.633Z
Have you looked at [smoothed analysis](http://arxiv.org/abs/cs/0111050)? This work not only addresses the average-case running time, but also the average-case stability.
Peter Shor 
<ds.algorithms><reference-request><optimization><linear-programming><na.numerical-analysis>
Numerical stability of Simplex method
shuhalo
# Numerical stability of Simplex method

(Asked by: username_0 on 2013-01-22)

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?

**Tags:** ds.algorithms, reference-request, optimization, linear-programming, na.numerical-analysis
> **Comments:**
> **username_1**: If you are interested in implementations of the simplex algorithm, then I would suggest you to ask the question in http://www.or-exchange.com/  
> **username_0**: @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.  
> **username_0**: I have edited the question to make my interest clearer.  
> **username_2**: Have you looked at [smoothed analysis](http://arxiv.org/abs/cs/0111050)? This work not only addresses the average-case running time, but also the average-case stability.  

---

## 1 answers

### Answer by username_3 on 2014-06-06. Score: 3

Yes, there is research on this issue.

[The Simplex Method is Not Always Well Behaved](http://www.ia.pw.edu.pl/~wogrycza/publikacje/artykuly/mylinalg.pdf), Wlodzimierz Ogryczak

[retroLP, An Implementation of the Standard Simplex Method](http://cis.poly.edu/rvslyke/implmnt.pdf), Gavriel Yarmish and Richard Van Slyke

[A Numerically Stable Form of the Simplex Algorithm](http://www.sciencedirect.com/science/article/pii/0024379573900475), Philip E. Gill and Walter Murray

You might also be interested in the [revised simplex method](http://en.wikipedia.org/wiki/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](http://www.cise.ufl.edu/research/sparse/Morgan/index.htm).


---

