Predicting the Execution Time of the Primal and Dual Simplex Algorithms Using Artificial Neural Networks

Selection of the most efficient algorithm for a given set of linear programming problems has been a significant and, at the same time, challenging process for linear programming solvers. The most widely used linear programming algorithms are the primal simplex algorithm, the dual simplex algorithm, and the interior point method. Interested in algorithm selection processes in modern mathematical solvers, we had previously worked on using artificial neural networks to formulate and propose a regression model for the prediction of the execution time of the interior point method on a set of benchmark linear programming problems. Extending our previous work, we are now examining a prediction model using artificial neural networks for the performance of CPLEX's primal and dual simplex algorithms. Our study shows that, for the examined set of benchmark linear programming problems, a regression model that can accurately predict the execution time of these algorithms could not be formed. Therefore, we are proceeding further with our analysis, treating the problem as a classification one. Instead of attempting to predict exact values for the execution time of primal and dual simplex algorithms, our models estimate classes, expressed as time ranges, under which the execution time of each algorithm is expected to fall. Experimental results show a good performance of the classification models for both primal and dual methods, with the relevant accuracy score reaching 0.83 and 0.84, respectively.

Automated summary

The selection of the most efficient algorithm for linear programming problems is a significant and challenging process. Previous work used artificial neural networks to formulate a regression model for predicting the execution time of the interior point method. Extension of this work involves examining a prediction model for the performance of CPLEX's primal and dual simplex algorithms using artificial neural networks. The study found that accurate regression models could not be formed, leading to a focus on classification instead.