| Home  | About ScienceAsia  | Publication charge  | Advertise with us  | Subscription for printed version  | Contact us  
Editorial Board
Journal Policy
Instructions for Authors
Online submission
Author Login
Reviewer Login
Volume 43 Number 3
Volume 43 Number 2
Volume 43 Number 1
Volume 43S Number 1
Volume 42 Number 6
Volume 42S Number 1
Earlier issues
Volume 40 Number 2 Volume 40 Number 3 Volume 40 Number 4

previous article next article 1

Research articles

ScienceAsia 40(2014): 248-256 |doi: 10.2306/scienceasia1513-1874.2014.40.248


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.

Download PDF

1 Download 38 View


Department of Mathematics and Computer Science, Faculty of Science, Chulalongkorn University, Bangkok 10330 Thailand

* Corresponding author, E-mail: Krung.s@chula.ac.th

Received 5 Mar 2013, Accepted 27 Dec 2013