Comparing the Solvers for the Mixed Integer Linear Programming Problems and the Software Environments That Call Them

The paper presents a concept for comparing the solvers for the mixed integer linear programming problems and the software environments that call them. This concept involves multiple repetition of solving mathematical programming problems with the same initial data to take into account the fact that the computer operations time can be considered as random. It is also assumed to solve the mathematical programming problem with the same structure by varying the initial data to compare the solvers. The comparison is carried out for a number of practical mathematical programming problems. For example we consider the portfolio optimization problem with the probability criterion. Solvers CPLEX, Gurobi, MATLAB, SCIP are used in testing. The features of calling solvers in various software environments are described. In particular, a modification of the source codes for calling the CPLEX solver through the Opti Toolbox add-on in Matlab environment is provided. The components of the time required to obtain a solution for various solvers and software environments are described and studied in detail. It is shown that the operating time of the solver itself can be comparable to the time of reading data from files and the time of forming constraints in a mathematical programming problem.

Keywords

mixed integer linear programming; solver; comparison; software environment.

References

1. Ignatov A.N. On the Scheduling Problem of Cargo Transportation on a Railway Network Segment and Algorithms for its Solution. Bulletin of the South Ural State University. Series: Mathematical Modelling, Programming and Computer Software, 2021, vol. 14, no. 3, pp. 61-76. DOI: 10.14529/mmp210305
2. Ignatov A.N. On the Algorithm of Cargoes Transportation Scheduling in the Transport Network. Automation and Remote Control, 2023, vol. 84, no. 9, pp. 993-1004. DOI: 10.1134/S0005117923090096
3. Ignatov A.N., Naumov A.V. On the Problem of Increasing the Railway Station Capacity. Automation and Remote Control, 2021, vol. 82, no. 1, pp. 102-114. DOI: 10.1134/S0005117921010070
4. Ignatov A.N., Naumov A.V. On Time Selection for Track Possession Assignment at the Railway Station. Bulletin of the South Ural State University. Series: Mathematical Modelling, Programming and Computer Software, 2019, vol. 12, no. 3, pp. 5-16. DOI: 10.14529/mmp190301
5. Ye Yixin, Liang Shengming, Zhu Yushan. A Mixed-Integer Linear Programming-Based Scheduling Model for Refined-Oil Shipping. Computers and Chemical Engineering, 2017, vol. 99, pp. 106-116. DOI: 10.1016/j.compchemeng.2017.01.031
6. Flores-Luyo L., Agra A., Figueiredo R., Ocana E. Mixed Integer Formulations for a Routing Problem with Information Collection in Wireless Networks. European Journal of Operational Research, 2020, vol. 280, no. 2, pp. 621-638. DOI: doi.org/10.1016/j.ejor.2019.06.054
7. Yang Xiao, Bostel N., Dejax P. A MILP Model and Memetic Algorithm for the Hub Location and Routing Problem with Distinct Collection and Delivery Tours. Computers and Industrial Engineering, 2019, vol. 135, pp. 105-119. DOI: 10.1016/j.cie.2019.05.038
8. Benati S., Rizzi R. A Mixed Integer Linear Programming Formulation of the Optimal mean/Value-at-Risk Portfolio Problem. European Journal of Operational Research, 2007, vol. 176, no. 1, pp. 423-434. DOI: 10.1016/j.ejor.2005.07.020
9. Kibzun A.I., Ignatov A.N. Reduction of the Two-Step Problem of Stochastic Optimal Control with Bilinear Model to the Problem of Mixed Integer Linear Programming. Automation and Remote Control, 2016, vol. 77, no. 12, pp. 2175-2192. DOI: 10.1134/S0005117916120079
10. Ivanov S.V., Akmaeva V.N. Two-Stage Stochastic Facility Location Model with Quantile Criterion and Choosing Reliability Level. Bulletin of the South Ural State University. Series: Mathematical Modelling, Programming and Computer Software, 2021, vol. 14, no. 3, pp. 5-17. DOI: 10.14529/mmp210301
11. Albareda-Sambola M., Fernandez E., Hinojosa Y., Puerto J. The Multi-Period Incremental Service Facility Location Problem. Computers and Operations Research, 2009, vol. 36, no. 5, pp. 1356-1375. DOI: 10.1016/j.cor.2008.02.010
12. Ignatov A.N. On the Resource Allocation Problem to Increase Reliability of Transport Systems. Lecture Notes in Computer Science, 2023, vol. 13930, pp. 169-180. DOI: 10.1007/978-3-031-35305-5_11
13. Omu A., Choudhary R., Boies A. Distributed Energy Resource System Optimisation Using Mixed Integer Linear Programming. Energy Policy, 2013, vol. 61, pp. 249-266. DOI: 10.1016/j.enpol.2013.05.009
14. Knueven B., Ostrowski J., Watson J.-P. On Mixed-Integer Programming Formulations for the Unit Commitment Problem. INFORMS Journal on Computing, 2020, vol. 32, no. 4, pp. 857-876. DOI: 10.1287/ijoc.2019.0944
15. Veintimilla-Reyes J., Cattrysse D. Mixed Integer Linear Programming (MILP) Approach to Deal with Spatio-temporal Water Allocation. Procedia Engineering, 2016, vol. 162, pp. 221-229. DOI: 10.1016/j.proeng.2016.11.045
16. Anand R., Aggarwal D., Kumar V. A Comparative Analysis of Optimization Solvers. Journal of Statistics and Management Systems, 2017, vol. 20, no. 4, pp. 623-635. DOI: 10.1080/09720510.2017.1395182
17. Kronqvist J., Bernal Neira D.E., Lundell A., Grossmann I.E. A Review and Comparison of Solvers for Convex MINLP. Optimization and Engineering, 2019, vol. 20, no. 4, pp. 397-455. DOI: 10.1007/s11081-018-9411-8
18. Koch T., Berthold T., Pedersen J., Vanaret Ch. Progress in Mathematical Programming Solvers from 2001 to 2020. EURO Journal on Computational Optimization, 2022, vol. 10, no. 2, 32 p. DOI: 10.1016/j.ejco.2022.100031
19. Gleixner A., Hendel G., et al. MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library. Mathematical Programming Computation, 2021, vol. 13, pp. 443-490. DOI: 10.1007/s12532-020-00194-3
20. Ignatov A.N. On Solution of the Problem of Correcting Scalar Terminal State of an Aircraft for an Arbitrary Distribution of a Multiplicative Perturbation. Trudy MAI, 2016, no. 87, 19 p. (in Russian)
21. Dempe S., Ivanov S., Naumov A. Reduction of the Bilevel Stochastic Optimization Problem with Quantile Objective Function to a Mixed-Integer Problem. Applied Stochastic Models in Business and Industry, 2017, vol. 33, no. 5, pp. 544-554. DOI: 10.1002/asmb.2254
22. Ivanov S.V., Naumov A.V. Algorithm to Optimize the Quantile Criterion for the Polyhedral Loss Function and Discrete Distribution of Random Parameters. Automation and Remote Control, 2012, vol. 73, pp. 105-117. DOI: 10.1134/S0005117912010080
23. Borisov A., Ivanov A. Stochastic Time Complexity Surfaces of Computing Node. Mathematics, 2023, vol. 20, no. 11, pp. 43-79. DOI: 10.3390/math11204379
24. MacLean L.C., Thorp E.O., Zhao Yonggan, Ziemba W. How Does the Fortune's Formula Kelly Capital Growth Model Perform? The Journal of Portfolio Management Summer, 2011, vol. 37, no. 4, pp. 96-111. DOI: 10.3905/jpm.2011.37.4.096
25. Ziemba W.T., Wickson R.G. Stochastic Optimization Models in Finance. Singapore, World Scientific, 2006.
26. Alexander G.J., Baptista A.M. Portfolio Performance Evaluation Using Value at Risk. The Journal of Portfolio Management Summer, 2003, vol. 29, no. 4, pp. 93-102. DOI: 10.3905/jpm.2003.319898
27. Ignatov A.N. On the Construction of Positional Control in a Multistep Portfolio Optimization Problem with Probabilistic Criterion. Automation and Remote Control, 2020, vol. 81, pp. 2181-2193. DOI: 10.1134/S0005117920120036
28. SolversMILP. Available at: https://github.com/al-ignatov/SolversMILP_comparison (accessed on 02.05.2024)