| 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 48 Number 6
Volume 48 Number 5
Volume 48 Number 4
Volume 48 Number 3
Volume 48 Number 2
Volume 48S Number 1
Earlier issues
Volume 40 Number 2 Volume 40 Number 3 Volume 40 Number 4

previous article next article

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

13 Downloads 1170 Views

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