| Article ID: | iaor20031622 |
| Country: | Netherlands |
| Volume: | 30 |
| Issue: | 5 |
| Start Page Number: | 289 |
| End Page Number: | 294 |
| Publication Date: | Oct 2002 |
| Journal: | Operations Research Letters |
| Authors: | Gopalakrishnan Balaji, Barnes Earl, Chen Victoria, Johnson Ellis. L. |
| Keywords: | duality |
We have developed a least-squares primal–dual algorithm for solving linear programming problems that is impervious to degeneracy, with strict improvement attained at each iteration. We tested our algorithm on a range of linear programming problems including ones that require many pivots, usually because of degeneracy, using the primal simplex method and the dual simplex method with steepest edge pivoting. On average, our algorithm took less than half the number of iterations required by the primal and dual simplex methods; on some problems, it took over 30 times fewer iterations.