Steepest-edge simplex algorithms for linear programming |
| |
Authors: | John J. Forrest Donald Goldfarb |
| |
Affiliation: | (1) IBM Research Division, T.J. Watson Research Center, Yorktown Heights, NY, USA;(2) Department of Industrial Engineering and Operations Research, Columbia University, 10027-6699 New York, NY, USA |
| |
Abstract: | We present several new steepest-edge simplex algorithms for solving linear programming problems, including variants of both the primal and the dual simplex method. These algorithms differ depending upon the space in which the problem is viewed as residing, and include variants in which this space varies dynamically. We present computational results comparing steepest-edge simplex algorithms and approximate versions of them against simplex algorithms that use standard pivoting rules on truly large-scale realworld linear programs with as many as tens of thousands of rows and columns. These results demonstrate unambiguously the superiority of steepest-edge pivot selection criteria to other pivot selection criteria in the simplex method.The research of this author was supported in part by NSF Grants DMS 85-12277, DMS 91-0619 and CDR 84-21402. |
| |
Keywords: | Steepest-edge simplex method large-scale linear programming Devex variants |
本文献已被 SpringerLink 等数据库收录! |
|