Predicting the Execution Time of the Interior Point Method for Solving Linear Programming Problems Using Artificial Neural Networks

Deciding upon which algorithm would be the most efficient for a given set of linear programming problems is a significant step in linear programming solvers. CPLEX Optimizer supports primal and dual variants of the simplex algorithm and the interior point method. In this paper, we examine a prediction model using artificial neural networks for the performance of CPLEX’s interior point method on a set of benchmark linear programming problems (netlib, kennington, Mészáros, Mittelmann). Our study consists of the measurement of the execution time needed for the solution of 295 linear programming problems. Specific characteristics of the linear programming problems are examined, such as the number of constraints and variables, the nonzero elements of the constraint matrix and the right-hand side, and the rank of the constraint matrix of the linear programming problems. The purpose of our study is to identify a model, which could be used for prediction of the algorithm’s efficiency on linear programming problems of similar structure. This model can be used prior to the execution of the interior point method in order to estimate its execution time. Experimental results show a good fit of our model both on the training and test set, with the coefficient of determination value at 78% and 72%, respectively.