14
$\begingroup$

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.

Improve this question
$\endgroup$
1

5 Answers 5

Reset to default
13
$\begingroup$

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.

Improve this answer
$\endgroup$
12
$\begingroup$

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
Improve this answer
$\endgroup$
6
  • 12
    $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Commented Apr 15, 2011 at 6:40
  • 1
    $\begingroup$ Are there any distributed (like MPI) open source implementations of LP? $\endgroup$
    – Tomek Tarczynski
    Commented Apr 15, 2011 at 9:01
  • 3
    $\begingroup$ @Tomek LP is P-complete and unlikely to have an efficient parallelization. $\endgroup$
    – Marcus Ritt
    Commented Apr 15, 2011 at 11:17
  • $\begingroup$ @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 branchandcut.org and the strongly related COIN-OR web site: coin-or.org $\endgroup$
    – Massimo Cafaro
    Commented Apr 15, 2011 at 13:53
  • 9
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Commented Apr 16, 2011 at 4:17
9
$\begingroup$

Vanderbei's Linear Programming book 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...)

Improve this answer
$\endgroup$
6
$\begingroup$

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

However, in practice SM works well. This has been formalized by the introduction of smoothed analysis 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 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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.