An efficient approach to updating simplex multipliers in the simplex algorithm

作者：Hu Jian Feng; Pan Ping Qi^*

来源：Mathematical Programming, 2008, 114(2): 235-248.

DOI：10.1007/s10107-007-0099-3

• linear programming
• simplex algorithm
• simplex multipliers
• LU factorization
• Bartels-Golub update
• Forrest-Tomlin update

The simplex algorithm computes the simplex multipliers by solving a system (or two triangular systems) at each iteration. This note offers an efficient approach to updating the simplex multipliers in conjunction with the Bartels-Golub and Forrest-Tomlin updates for LU factors of the basis. It only solves one triangular system. The approach was implemented within and tested against MINOS 5.51 on 129 problems from Netlib, Kennington and BPMPD. Computational results show that the new approach improves simplex implementations.

• 出版日期2008-8
• 单位东南大学