Research

Improving the Efficiency of the Simplex Algorithm Based on a Geometric Explanation of Phase 1

Authors

Published

International Journal of Operational Research, 4 ed., vol. 5, pp. 408 - 428, January (1st Quarter/Winter) 2009

Abstract

An open question pertaining to the simplex algorithm is where phase 1 terminates on the feasible region. In this work, computer simulations support the conjecture that phase 1 terminates at a feasible point that is geometrically close in Euclidean distance to the starting point, when compared to other feasible solutions. This observation is exploited to develop a coordinate transformation for bounded linear programs (LP) that typically results in phase 1 ending at a feasible solution that is geometrically close to the optimal solution, thus requiring fewer iterations in phase 2 to solve the problem. This is confirmed by extensive computational experiments using CPLEX on randomly generated LPs and also on the problems in Netlib and shows generally increasing benefits as the number of negative coefficients in the original minimization objective function increases. Though not winning on all problems, the coordinate transformation saves an average of about 2% of the CPU time over all problems solved in Netlib and about 11% on problems having more than 10% negative coefficients in the minimization objective function.

Daniel Solow