ScienceAsia 40(2014): 248-256 |doi:
Max-out-in pivot rule with cycling prevention for the simplex method
Monsicha Tipawanna, Krung Sinapiromsaran*
ABSTRACT: A max-out-in pivot rule is designed to solve a linear programming (LP) problem with a non-zero right-hand side vector. It identifies the maximum of the leaving basic variable before selecting the associated entering nonbasic variable. Our method guarantees convergence after a finite number of iterations. The improvement of our pivot rule over Bland's rule is illustrated by some cycling LP examples. In addition, we report computational results obtained from two sets of LP problems. Among 100 simulated LP problems, the max-out-in pivot rule is significantly better than Bland's rule and Dantzig's rule according to the Wilcoxon signed rank test. Based on these results, we conclude that our method is best suited for degenerate LP problems.
1 Download 38 View
|Department of Mathematics and Computer Science, Faculty of Science, Chulalongkorn University, Bangkok 10330 Thailand
* Corresponding author, E-mail: Krung.firstname.lastname@example.org
Received 5 Mar 2013, Accepted 27 Dec 2013