<p>I strongly recommend the paper by Bixby, the "father" of CPLEX, that surveys not only on implementing aspects of the (revised) simplex algorithm: <strong>Robert E. Bixby</strong>, <em>Solving Real-World Linear Programs: A Decade and More of Progress</em>, <a href="http://or.journal.informs.org/content/50/1/3.abstract">Operations Research (50) 2002, 3-15</a>.</p>

CC BY-SA 3.0
2013-01-24T14:21:41.007Z
2013-01-24T14:21:41.007Z
vb le
<p>The simplex algorithm is not in P. CLRS therefore states that, even though in practice it works "well", there are some inputs causing the algorithm to run in exponential time. This is strictly related to the algorithm, not to its implementation: you will face this independently of how exactly you implement the algorithm. However, LP is in P. This was proved by Khachian in 1979, however his ellipsoid algorithm is not practical. Today, interior points methods are widely used. The first one was discovered by Karmarkar in 1984.</p>

<p>If you are interested in practical implementations, take a look at:</p>

<p>GUROBI, free for academic use, is right now the best optimizer available (both sequential and shared-memory parallel versions):</p>

<p><a href="http://www.gurobi.com" rel="nofollow noreferrer">http://www.gurobi.com</a></p>

<p>the GLPK library:</p>

<p><a href="http://www.gnu.org/software/glpk/" rel="nofollow noreferrer">http://www.gnu.org/software/glpk/</a></p>

<p>this is an open source project, providing implementations for:</p>

<ul>
<li>primal and dual simplex methods</li>
<li>primal-dual interior-point method</li>
<li>branch-and-cut method</li>
<li>translator for GNU MathProg </li>
<li>application program interface (API)</li>
<li>stand-alone LP/MIP solver</li>
</ul>

CC BY-SA 3.0
2011-04-15T06:40:04.370Z
Indeed. I'd strongly recommend NOT trying to implement simplex by yourself, unless that's the whole point of the exercise. If you just want to use it, off the shelf methods are much better. Also, CPLEX is free for academic use if that's appropriate for you.
Suresh Venkat
CC BY-SA 3.0
2011-04-15T09:01:48.350Z
Are there any distributed (like MPI) open source implementations of LP?
Tomek Tarczynski
CC BY-SA 3.0
2011-04-15T11:17:18.647Z
@Tomek LP is P-complete and unlikely to have an efficient parallelization.
Marcus Ritt
CC BY-SA 3.0
2011-04-15T13:53:04.163Z
@Tomek: Simphony provides a distributed version that currently runs in any environment supported by the PVM message passing protocol (MPI is not yet supported). The same source code can also be compiled for shared-memory architectures using any OpenMP compliant compiler.. See http://branchandcut.org/ and the strongly related COIN-OR web site: http://www.coin-or.org/
Massimo Cafaro
CC BY-SA 3.0
2011-04-15T15:09:58.157Z
@Marcus: I know that LP is P-complete, but still for large problems and relatively small number of processors almost linear speedup should be achievable.
@unforgiven: Thanks, it looks promising.
Tomek Tarczynski
CC BY-SA 3.0
2011-04-16T04:17:14.060Z
CPLEX is probably the best implementation of LP currently available (that's why people pay so much for it), but pretty much all of the widely used implementations will do substantially better than anything you program yourself. This includes the Mathematical, Maple, and MATLAB packages. There are lots of implementations around, including some fairly good free ones (QSopt, for one, which is free if you're not planning to use it for commercial purposes), so programming it yourself is only worthwhile for the learning experience.
Peter Shor 
CC BY-SA 3.0
2011-04-15T06:35:12.830Z
2017-04-27T17:46:20.197Z
2017-04-27T17:46:20.197Z
Massimo Cafaro
<p>Vanderbei's Linear Programming <a href="http://www.princeton.edu/~rvdb/LPbook/" rel="nofollow noreferrer">book</a> goes through many of the low level details... But as the other answers/comments suggested, implementing LP solver is a hard and thankless task. Off the shelf solver is probably the way to go... (There are also some open source LP solvers...)</p>

CC BY-SA 3.0
2011-04-16T21:57:16.470Z
2017-04-26T20:49:48.773Z
2017-04-26T20:49:48.773Z
Sariel Har-Peled
<p>It is not only naive implementations that sometimes behave in exponential time. In fact, I think all known deterministic and randomized rules have super-polynomial worst case inputs. Most of the known inputs that produce this worst-case behavior are highly structured, a related question:</p>

<p><a href="https://cstheory.stackexchange.com/questions/2498/the-structure-of-pathological-instances-for-simplex-algorithms">The structure of pathological instances for simplex algorithms</a></p>

<p>However, in practice SM works well. This has been formalized by the introduction of <a href="http://arxiv.org/abs/cs/0111050v7" rel="nofollow noreferrer">smoothed analysis</a> which is basically worst-case analysis with slightly perturbed inputs. Under this analysis, SM is polytime, in other words, for every input (even the pathological ones) there is a slight perturbation that allows the algorithm to perform well. This insight has been transformed into a <a href="http://portal.acm.org/citation.cfm?doid=1132516.1132524" rel="nofollow noreferrer">randomized algorithm</a> that performs in polytime. However, as far as I understand, there is still some debate about whether this algorithm qualifies as a 'true' simplex algorithm. I am also unaware if standard packages implement something along the lines of this, but you should be able to find some implementation if you search around, on account of the result being 5+ years old.</p>

CC BY-SA 3.0
2011-04-16T20:41:26.947Z
2011-04-16T20:41:26.947Z
2017-04-13T12:32:28.167Z
Artem Kaznatcheev
<p>You might check Luenberger, Ye, Linear and Nonlinear Programming, 3rd ed. That seems pretty comprehensive, but I haven't made it far enough yet to say whether it completely answers your question.</p>

CC BY-SA 3.0
2011-04-15T17:54:02.430Z
2011-04-15T17:54:02.430Z
marshallf
<p>I'm interested in implementing SM for LP task, however I've heard about possible pitfalls: Cormen's book says that it is possible to have input data which will make naive implementation to behave in exponential time. I've also heard that naive implementation can loop for some kind of data. </p>

<p>Is there a book/paper/source which explains nuances of practical implementation of SM?</p>

<p>Thanks in advance.</p>

CC BY-SA 3.0
2011-04-16T09:22:47.110Z
Loop: see http://en.wikipedia.org/wiki/Bland's_rule
Maverick Woo
<ds.algorithms><linear-programming><software><implementation><simplex>
Best book on Simplex Method implementation?
lithuak
# Best book on Simplex Method implementation?

(Asked by: username_0 on 2011-04-14)

I'm interested in implementing SM for LP task, however I've heard about possible pitfalls: Cormen's book says that it is possible to have input data which will make naive implementation to behave in exponential time. I've also heard that naive implementation can loop for some kind of data.

Is there a book/paper/source which explains nuances of practical implementation of SM?

Thanks in advance.

**Tags:** ds.algorithms, linear-programming, software, implementation, simplex

> **Comments:**
> **username_1**: Loop: see http://en.wikipedia.org/wiki/Bland's_rule  

---

## 5 answers

### Answer by username_2 on 2013-01-24. Score: 13

I strongly recommend the paper by Bixby, the "father" of CPLEX, that surveys not only on implementing aspects of the (revised) simplex algorithm: **Robert E. Bixby**, *Solving Real-World Linear Programs: A Decade and More of Progress*, [Operations Research (50) 2002, 3-15](http://or.journal.informs.org/content/50/1/3.abstract).


---

### Answer by username_3 on 2011-04-15. Score: 12

The simplex algorithm is not in P. CLRS therefore states that, even though in practice it works "well", there are some inputs causing the algorithm to run in exponential time. This is strictly related to the algorithm, not to its implementation: you will face this independently of how exactly you implement the algorithm. However, LP is in P. This was proved by Khachian in 1979, however his ellipsoid algorithm is not practical. Today, interior points methods are widely used. The first one was discovered by Karmarkar in 1984.

If you are interested in practical implementations, take a look at:

GUROBI, free for academic use, is right now the best optimizer available (both sequential and shared-memory parallel versions):

<http://www.gurobi.com>

the GLPK library:

<http://www.gnu.org/software/glpk/>

this is an open source project, providing implementations for:

* primal and dual simplex methods
* primal-dual interior-point method
* branch-and-cut method
* translator for GNU MathProg
* application program interface (API)
* stand-alone LP/MIP solver

> **Comments:**
> **username_4**: Indeed. I'd strongly recommend NOT trying to implement simplex by yourself, unless that's the whole point of the exercise. If you just want to use it, off the shelf methods are much better. Also, CPLEX is free for academic use if that's appropriate for you.  
> **username_5**: Are there any distributed (like MPI) open source implementations of LP?  
> **username_6**: @Tomek LP is P-complete and unlikely to have an efficient parallelization.  
> **username_3**: @Tomek: Simphony provides a distributed version that currently runs in any environment supported by the PVM message passing protocol (MPI is not yet supported). The same source code can also be compiled for shared-memory architectures using any OpenMP compliant compiler.. See http://branchandcut.org/ and the strongly related COIN-OR web site: http://www.coin-or.org/  
> **username_5**: @Marcus: I know that LP is P-complete, but still for large problems and relatively small number of processors almost linear speedup should be achievable. @unforgiven: Thanks, it looks promising.  
> **username_7**: CPLEX is probably the best implementation of LP currently available (that's why people pay so much for it), but pretty much all of the widely used implementations will do substantially better than anything you program yourself. This includes the Mathematical, Maple, and MATLAB packages. There are lots of implementations around, including some fairly good free ones (QSopt, for one, which is free if you're not planning to use it for commercial purposes), so programming it yourself is only worthwhile for the learning experience.  

---

### Answer by username_8 on 2011-04-16. Score: 9

Vanderbei's Linear Programming [book](http://www.princeton.edu/~rvdb/LPbook/) goes through many of the low level details... But as the other answers/comments suggested, implementing LP solver is a hard and thankless task. Off the shelf solver is probably the way to go... (There are also some open source LP solvers...)


---

### Answer by username_9 on 2011-04-16. Score: 6

It is not only naive implementations that sometimes behave in exponential time. In fact, I think all known deterministic and randomized rules have super-polynomial worst case inputs. Most of the known inputs that produce this worst-case behavior are highly structured, a related question:

[The structure of pathological instances for simplex algorithms](https://cstheory.stackexchange.com/questions/2498/the-structure-of-pathological-instances-for-simplex-algorithms)

However, in practice SM works well. This has been formalized by the introduction of [smoothed analysis](http://arxiv.org/abs/cs/0111050v7) which is basically worst-case analysis with slightly perturbed inputs. Under this analysis, SM is polytime, in other words, for every input (even the pathological ones) there is a slight perturbation that allows the algorithm to perform well. This insight has been transformed into a [randomized algorithm](http://portal.acm.org/citation.cfm?doid=1132516.1132524) that performs in polytime. However, as far as I understand, there is still some debate about whether this algorithm qualifies as a 'true' simplex algorithm. I am also unaware if standard packages implement something along the lines of this, but you should be able to find some implementation if you search around, on account of the result being 5+ years old.


---

### Answer by username_10 on 2011-04-15. Score: 1

You might check Luenberger, Ye, Linear and Nonlinear Programming, 3rd ed. That seems pretty comprehensive, but I haven't made it far enough yet to say whether it completely answers your question.


---

