An efficient approach to updating simplex multipliers in the simplex algorithm

• 成果类型: Article
• 署名作者: Hu, Jian-Feng; Pan, Ping-Qi
• 署名单位: Southeast University - China
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-007-0099-3
• 发表日期: 2008
• 页码: 235-248
• 关键词: decomposition

摘要

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.