# (587d) Accelerating the Simplex Algorithm Via Novel Crash Procedures

- Conference: AIChE Annual Meeting
- Year: 2016
- Proceeding: 2016 AIChE Annual Meeting
- Group: Computing and Systems Technology Division
- Session:
- Time:
Wednesday, November 16, 2016 - 4:14pm-4:32pm

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...

[6] Dongarra, J., Sullivan, F. (2000). Guest editorsâ?? introduction: The top 10 algorithms. Computing in Science & Engineering, 2(1), 22-23.