In a recent Subject To podcast featuring Bob Vanderbei, then Bob mentions a primal-dual simplex algorithm. Bob also discusses the algorithm in his Linear programming book and has been teaching it. It is clear from the podcast that he really likes this algorithm.
Now I have recently also gotten interested in that algorithm for the following reasons:
- It is a single phase algorithm that is trivial to start.
- At least in theory it has no problems with degeneracy given an easy to satisfy condition holds.
- It has a convergence measure that monotonically decreases to zero.
- Given a nondegeneracy assumption is satisfied then the primal basic variables and the dual nonbasic variables are strictly positive i.e. are in the interior.
- Moreover, the primal and dual infeasibility measures are reduced at the same rate.
- Therefore, in some sense it seems closely related to the homogenous model that is employed in interior-point methods.
In version 1 of Bob's LP book, Bob attributes the algorithm to G. B. Dantzig and references his famous 1963 book. Now Bob also mentions that that the algorithm is a special case of Lemke's algorithm for linear complementarity problems published in 1965. This fact has been proved by Irv Lustig as mentioned in his ph.d. thesis from 1987.
I have been searching for computational results for the primal-dual simplex algorithm but have not located much beyond what is presented by Vanderbei. One exception is the previously mentioned ph.d. thesis of Lustig that contains some of the very limited computational experiences with the primal-dual simplex algorithm. Note how few and small problems Lustig reports results back in 1987.
Nimrod Megiddo has an interesting paper showing that many seemingly different algorithms can be seen as a special case of the primal-dual simplex algorithm. The basic idea is that by choosing the initial perturbation employed by the primal-dial simplex algorithm appropriately the behavior of the other algorithms can be recovered. I doubt that for instance the dual simplex algorithm using steepest-edge pricing is a special case though.
I shall not claim that the primal-dual simplex algorithm is better in practice than the well known primal and dual simplex algorithms. However, from a theoretical point of view I find the primal-dual simplex algorithm much more pleasing.
I may add more material to this blog post later.
