467664 Accelerating the Simplex Algorithm Via Novel Crash Procedures
We propose novel crash procedures for finding an initial basis for the simplex algorithm. The main idea is to obtain a starting basis that is sparse and will reduce the fill-ins in LU factorization that forms the core operation of simplex iterations. We present extensive computational comparisons on standard benchmarks by supplying our initial basis to the state-of-the-art linear programming code CPLEX. The computations demonstrate that, in comparison to the CPLEX default crash procedure, our initialization strategy on average reduces the running time of CPLEX by 60% in the case of primal simplex and by 27% in the case of dual simplex. For large and difficult instances, our algorithm reduces the running time of CPLEX by an order of magnitude.
References cited:
[1] Dantzig, G. B. (1963). Linear programming and extensions. Princeton, NJ: Princeton University Press.
[2] D. Bertsimas and J. Tsitsiklis (1997). Introduction to Linear Optimization. Athena Scientific, Boston, MA.
[3] Bixby, R. E. (2002). Solving real-world linear programs: A decade and more of progress. Operations research, 50, 3–15.
[4] Bixby, R. E. (2012). A brief history of linear and mixed-integer programming computation. Documenta
Mathematica, 107–121.
[5] IBM (2016). IBM ILOG CPLEX V12.6. Available online: http://www.ibm.com/support/knowledgecenter/SSSA5P_12.6.0/ilog.odms.cplex.help/CPLEX/homepages/CPLEX.html
[6] Dongarra, J., Sullivan, F. (2000). Guest editors’ introduction: The top 10 algorithms. Computing in Science & Engineering, 2(1), 22-23.
See more of this Group/Topical: Computing and Systems Technology Division