5
$\begingroup$

I haven't really kept myself up to date with research on the simplex algorithm for several years. I have taught linear programming, but it has not focused on the cutting edge of things.

I remember many years ago I went to a course on linear programming, where the teacher said something along the lines of "When applying the simplex algorithm, its frustrating that we can "see" the optimal vertex all the time (convex feasible set) but we have to travel all the way around the edge of the polyhedron to get there".

My question is "what ideas have been proposed to make "short cuts" through the polyhedron when using the simplex algorithm"?

I know this is what interior point algorithms do, but this is in the context of the simplex algorithm.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

The only methods I can think of that could be interpreted as "taking a shortcut through the polyhedron" are:

  1. Cross-cross methods

  2. The Improved Primal Simplex Method for Degenerate LPs

In both cases the interpretation is a bit of a stretch.

This does not mean that simplex algorithms have not been improved in the recent years. On the implementation side, a lot of improvements went into presolve (one of those is folding), improved implementation details in all aspects of the algorithms, improved accuracy of the solves. My impression is that especially crossover has improved a lot recently (as can be seen in the Mittelmann benchmarks). Sadly, most of these improvements are done at solver companies and solver developers usually don't have much time to also publish their work in scientific journals.

Improve this answer
$\endgroup$
1

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.