Article ID: | iaor200968918 |
Country: | United Kingdom |
Volume: | 5 |
Issue: | 4 |
Start Page Number: | 408 |
End Page Number: | 428 |
Publication Date: | May 2009 |
Journal: | International Journal of Operational Research |
Authors: | Solow Daniel, Halim Hans |
Keywords: | simplex algorithm |
An open question pertaining to the simplex algorithm is where phase 1 terminates on the feasible region. Here, computer simulations support the conjecture that phase 1 terminates at a feasible point geometrically close to the starting point. This observation leads to a coordinate transformation for bounded Linear Programs (LP) that requires fewer iterations in phase 2. This is confirmed by computational experiments on random LPs and Netlib problems and shows generally increasing benefits as the number of negative coefficients in the minimisation objective function increases. Though not winning on all Netlib problems, the coordinate transformation saves 2–11% of the CPU time.