3
1

I read of different kinds of simplex method implementation here: The paper dates back to 1997.

In the paper the following implementations are discussed:

  1. The Revised Simplex Method
  2. The Bartels-Golub Method
  3. The Sparse Bartels-Golub Method
  4. Forrest-Tomlin Method
  5. Reid’s Method

Which of these implementation do commerical/open source solvers today use?

And are there new improved implementations that evolved in recent time or what changed? (Any papers?)

What are the disadvantage of QR-Factorization / Multigrid / Iterative Solvers for the simplex method?

asked 29 Apr '15, 14:55

opt3's gravatar image

opt3
615
accept rate: 0%

A very good reference here is Achim Koberstein's thesis (http://digital.ub.uni-paderborn.de/hs/content/titleinfo/3885).

(30 Apr '15, 14:09) Miles

The revised simplex method is a general description of the simplex method as actually implemented in most decent LP codes. It is contrasted with "tableau" or "dictionary" methods, which are useful for solving small examples by hand, but not much else, because they record and update far too much redundant information. Your items 2-5 are techniques for updating the basis matrix factorization in the revised simplex method. What you might be thinking when you write your item 1 is the "product form" update, which is the most straightforward to describe.

The nominal update of the basis inverse involves multiplication of the current iterate's inverse by an "eta" matrix, which describes the row operations necessary to produce the new inverse from the current one. The product form update doesn't actually perform the multiplication--instead it just records those matrices (actually, their inverses) and solves the resulting system using sparse forward and backward substitution. Decent simplex codes don't use this method. Because the matrix pivot is dictated by the simplex pivot, the method can be numerically unstable and may not be as sparse (so as fast) as possible.

The other methods you list are various types of "rank-1" updates, which attempt to preserve sparsity and stability. They are implemented similarly to the product form, in that the matrix transformations are recorded and the solves iterate through the transformations. Every so often, when the transformation lists get long, the basis is refactored from scratch and the process starts again. There is also a factorization and an update by Suhl and Suhl, which are pretty effective. I don't have an inventory of which codes use which of these methods, but there is a good introduction to how they work in Chvatal's Linear Programming book (except for the Suhl and Suhl one) and more detailed descriptions in Maros's book on implementing the simplex method.

QR and iterative methods are generally too slow and don't lend themselves easily to the sort of updating from iteration to iteration that is critical to simplex method performance.

link

answered 29 Apr '15, 16:37

Matthew%20Saltzman's gravatar image

Matthew Salt... ♦
4.7k310
accept rate: 17%

I think all commercial codes uses a variants of the FT update. See

Suhl, U.H., Suhl, L.M.: A fast LU update for linear programming. Annals of Operations Research 43(1), 33–47 (1993)

for more info.

link

answered 30 Apr '15, 02:25

Erling_MOSEK's gravatar image

Erling_MOSEK
61614
accept rate: 3%

That's the citation for one of the Suhl and Suhl papers I mentioned. Thanks.

(30 Apr '15, 09:26) Matthew Salt... ♦
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×231
×20

Asked: 29 Apr '15, 14:55

Seen: 1,029 times

Last updated: 30 Apr '15, 14:09

OR-Exchange! Your site for questions, answers, and announcements about operations research.