(587d) 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.
 Dantzig, G. B. (1963). Linear programming and extensions. Princeton, NJ: Princeton University Press.
 D. Bertsimas and J. Tsitsiklis (1997). Introduction to Linear Optimization. Athena Scientific, Boston, MA.
 Bixby, R. E. (2002). Solving real-world linear programs: A decade and more of progress. Operations research, 50, 3â??15.
 Bixby, R. E. (2012). A brief history of linear and mixed-integer programming computation. Documenta
 IBM (2016). IBM ILOG CPLEX V12.6. Available online: http://www.ibm.com/support/knowledgecenter/SSSA5P_12.6.0/ilog.odms.cplex...
 Dongarra, J., Sullivan, F. (2000). Guest editorsâ?? introduction: The top 10 algorithms. Computing in Science & Engineering, 2(1), 22-23.