Proof-of-concept implementation of the (dual) simplex algorithm for linear programming in Julia. It's not guaranteed to solve your problem, but it can solve some NETLIB instances.
This is not a textbook implementation and contains some advanced features that are important for practical implementations, such as:
- Stabilizing 2-pass ratio test
- Dual steepest-edge pricing
- Cost shifting for anti-degeneracy and numerical stability
- LU factorized basis matrix with product-form updates
For the expert audience, here's what's needed before we can compete with state-of-the-art implementations:
- Bound-flipping ratio test
- Internal rescaling and anti-degeneracy perturbations
- Primal simplex implementation (for clean up)
- Markowitz-type LU factorization
- Suhl-Suhl (Forrest-Tomlin)-style updates
- Exploitation of hyper-sparsity
- Presolve
There is no reason to use this code to solve real problems. It's here as a proof of concept of a large, complex application in Julia. Both algorithmic and performance-tuning contributions are welcome.
Current timings for test.jl solving GREENBEA.SIF on a laptop (Intel i5-3320M):
- jlSimplex: 9.83 seconds
- GLPK: 1.39 seconds
jlSimplex is released under the terms of the MIT license.