Journal of Applied Mathematics and Decision Sciences
Volume 2006 (2006), Article ID 76187, 11 pages
doi:10.1155/JAMDS/2006/76187
A computational approach to pivot selection in the LP relaxation
of set problems
Department of Mathematics, Faculty of Science, Kurdistan University, P.O. Box 416, Sanandaj 66177, Iran
Received 30 January 2006; Revised 17 July 2006; Accepted 10 October 2006
Copyright © 2006 F. Djannaty and B. Rostamy. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
It has long been known to the researchers that choosing a variable having the most negative reduced cost as the entering variable is not the best choice in the simplex method as shown by Harris (1975). Thus, suitable modifications in the pivot selection criteria may enhance the algorithm. Previous efforts such as that by Dantzig and steepest-edge rules for pivot selection are based on finding a unified strategy for entering variable in all linear programming problems. In the present work, a number of strategies for pivot selection in the LP relaxation of the set problems are proposed which consider the specific knowledge of the problem. A significant reduction in the number of iterations is achieved for a set of randomly generated test problems.