A largest-distance pivot rule for the simplex algorithm |
| |
Authors: | Ping-Qi Pan |
| |
Institution: | Department of Mathematics, Southeast University, Nanjing 210096, People’s Republic of China |
| |
Abstract: | We propose a new pivot rule for the simplex algorithm, which is demonstrative in the dual space intuitively. Although it is based on normalized reduced costs, like the steepest-edge rule and its variants, the rule is much simpler and cheaper than the latter. We report computational results obtained with the 47 largest Netlib problems in terms of the number of rows and columns, all of the 16 Kennington problems, and the 17 largest BPMPD problems. Over the total 80 problems, a variant of the rule outperformed the Devex rule with iterations and time ratio 1.43 and 3.24, respectively. |
| |
Keywords: | Large-scale linear programming Simplex algorithm Pivot rule Largest-distance Scaling |
本文献已被 ScienceDirect 等数据库收录! |
|