Computational aspects of simplex and MBU-simplex algorithms using different anti-cycling pivot rules

Abstract

Several variations of index selection rules for simplex-type algorithms for linear programming, like the Last-In-First-Out or the Most-Often-Selected-Variable are rules not only theoretically finite, but also provide significant flexibility in choosing a pivot element. Based on an implementation of the primal simplex and the monotonic build-up (MBU) simplex method, the practical benefit of the flexibility of these anti-cycling pivot rules is evaluated using public benchmark LP test sets. Our results also provide numerical evidence that the MBU-simplex algorithm is a viable alternative to the traditional simplex algorithm.

Keywords:

• monotonic build-up simplex algorithm
• primal simplex method
• index selection rules
• linear programming

AMS Subject Classification:

• 90C05

Acknowledgments

This research has been supported by the TÁMOP-4.2.1./B-09/1/KMR-2010-0002, Hungarian National Office of Research and Technology with the financial support of the European Union from the European Social Fund. Tibor Illés acknowledges the research support obtained from Strathclyde University, Glasgow under the John Anderson Research Leadership Program.

We are grateful to Zsolt Csizmadia from FICO for the technical support related to Xpress. We are also grateful for the anonymous referees for the many helpful and constructive comments that helped to improve the quality of the paper.

Notes

The authors are grateful to an anonymous referee for suggesting this form for presenting the results.