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

В работе приводится концепция сравнения решателей задач смешанного целочисленного линейного программирования и вызывающих их программных сред. Эта концепция предполагает многократное повторение решения задач математического программирования с одними и теми же исходными данными для учета того, что время выполнения операций компьютером можно рассматривать как случайное. Для сравнения решателей также предполагается варьировать исходные данные при решении задачи математического программирования той же структуры. Сравнение проводится для ряда практических задач математического программирования. Например, рассматривается задача оптимизации портфеля ценных бумаг с вероятностным критерием. В тестировании используются решатели CPLEX, Gurobi, MATLAB, SCIP. В работе разбираются особенности вызова решателей в различных программных средах. В частности, описывается модификация исходных кодов для вызова решателя CPLEX через надстройку Opti Toolbox в среде Matlab. Детально описываются и исследуются компоненты времени получения решения для различных решателей и программных сред. Показывается, что время работы самого решателя может быть сравнимо со временем чтения данных из файлов и временем формирование ограничений в задаче математического программирования.

Ключевые слова

смешанное целочисленное линейное программирование; решатель; сравнение; программная среда.

Литература

1. Игнатов, А.Н. О задаче составления расписания грузоперевозок на участке железнодорожной сети и алгоритмах ее решения / А.Н. Игнатов // Вестник ЮУрГУ. Серия: Математическое моделирование и программирование. - 2021. - Т. 14, № 3. - С. 61-76.
2. Ignatov, A.N. On the Algorithm of Cargoes Transportation Scheduling in the Transport Network / A.N. Ignatov // Automation and Remote Control. - 2023. - V. 84, № 9. - P. 993-1004.
3. Ignatov, A.N. On the Problem of Increasing the Railway Station Capacity / A.N. Ignatov, A.V. Naumov // Automation and Remote Control. - 2021. - V. 82, № 1. - P. 102-114.
4. Игнатов, А.Н. О выборе времени для установления "технологического окна " на железнодорожной станции / А.Н. Игнатов, А.В. Наумов // Вестник ЮУрГУ. Серия: Математическое моделирование и программирование. - 2019. - Т. 12, № 3. - С. 5-16.
5. Ye, Yixin. A Mixed-Integer Linear Programming-Based Scheduling Model for Refined-Oil Shipping / Yixin Ye, Shengming Liang, Yushan Zhu // Computers and Chemical Engineering. - 2017. - V. 99. - P. 106-116.
6. Flores-Luyo, L. Mixed Integer Formulations for a Routing Problem with Information Collection in Wireless Networks / L. Flores-Luyo, A. Agra, R. Figueiredo, E. Ocana // European Journal of Operational Research. - 2020. - V. 280, № 2. - P. 621-638.
7. Yang, Xiao. A MILP Model and Memetic Algorithm for the Hub Location and Routing Problem with Distinct Collection and Delivery Tours / Xiao Yang, N. Bostel, P. Dejax // Computers and Industrial Engineering. - 2019. - V. 135. - P. 105-119.
8. Benati, S. A Mixed Integer Linear Programming Formulation of the Optimal Mean/Value-at-Risk Portfolio Problem / S. Benati, R. Rizzi // European Journal of Operational Research. - 2007. - V. 176, № 1. - P. 423-434.
9. Kibzun, A.I. Reduction of the Two-Step Problem of Stochastic Optimal Control with Bilinear Model to the Problem of Mixed Integer Linear Programming / A.I. Kibzun, A.N. Ignatov // Automation and Remote Control. - 2016. - V. 77, № 12. - P. 2175-2192.
10. Иванов, С.В. Двухэтапная стохастическая модель размещения предприятий с квантильным критерием и выбором уровня надежности / С.В. Иванов, В.Н. Акмаева // Вестник ЮУрГУ. Серия: Математическое моделирование и программирование. - 2021. - V. 14, № 3. - P. 5-17.
11. Albareda-Sambola, M. The Multi-Period Incremental Service Facility Location Problem / M. Albareda-Sambola, E. Fernandez, Y. Hinojosa, J. Puerto // Computers and Operations Research. - 2009. - V. 36, № 5. - P. 1356-1375.
12. Ignatov, A.N. On the Resource Allocation Problem to Increase Reliability of Transport Systems / A.N. Ignatov // Lecture Notes in Computer Science. - 2023. - V. 13930. - P. 169-180.
13. Omu, A. Distributed Energy Resource System Optimisation Using Mixed Integer Linear Programming / A. Omu, R. Choudhary, A. Boies // Energy Policy. - 2013. - V. 61. - P. 249-266.
14. Knueven, B. On Mixed-Integer Programming Formulations for the Unit Commitment Problem / B. Knueven, J. Ostrowski, J.-P. Watson // INFORMS Journal on Computing. - 2020. - V. 32, № 4. - P. 857-876.
15. Veintimilla-Reyes, J. Mixed Integer Linear Programming (MILP) Approach to Deal with Spatio-Temporal Water Allocation / J. Veintimilla-Reyes, D. Cattrysse // Procedia Engineering. - 2016. - V. 162. - P. 221-229.
16. Anand, R. A Comparative Analysis of Optimization Solvers / R. Anand, D. Aggarwal, V. Kumar // Journal of Statistics and Management Systems. - 2017. - V. 20, № 4. - P. 623-635.
17. Kronqvist, J. A Review and Comparison of Solvers for Convex MINLP / J. Kronqvist, D. Bernal Neira, A. Lundell, I.E. Grossmann // Optimization and Engineering. - 2019. - V. 20. - P. 397-455.
18. Koch, T. Progress in Mathematical Programming Solvers from 2001 to 2020 / T. Koch, T. Berthold, J. Pedersen, Ch. Vanaret // EURO Journal on Computational Optimization. - 2022. - V. 10, № 2. - 32 p.
19. Gleixner, A. MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library / A. Gleixner, G. Hendel, et al. // Mathematical Programming Computation. - 2021. - V. 13. - P. 443-490.
20. Игнатов, А.Н. О решении задачи корректирования скалярного терминального состояния летательного аппарата при произвольном распределении мультипликативного возмущения / А.Н. Игнатов // Труды МАИ. - 2016. - №. 87. - 19 c.
21. Dempe, S. Reduction of the Bilevel Stochastic Optimization Problem with Quantile Objective Function to a Mixed-Integer Problem / S. Dempe, S. Ivanov, A. Naumov // Applied Stochastic Models in Business and Industry. - 2017. - V. 33, № 5. - P. 544-554.
22. Ivanov S.V. Algorithm to Optimize the Quantile Criterion for the Polyhedral Loss Function and Discrete Distribution of Random Parameters / S.V. Ivanov, A.V. Naumov // Automation and Remote Control. - 2012. - V. 73. - P. 105-117.
23. Borisov, A. Stochastic Time Complexity Surfaces of Computing Node / A. Borisov, A. Ivanov // Mathematics. - 2023. - V. 20, № 11. - P. 43-79.
24. MacLean, L.C. How does the fortune's formula Kelly capital growth model perform? / L.C. MacLean, E.O. Thorp, Yonggan Zhao, W. Ziemba // The Journal of Portfolio Management Summer. - 2011. - V. 37, № 4. - P. 96-111.
25. Ziemba, W.T. Stochastic Optimization Models in Finance / W.T. Ziemba, R.G. Wickson. - Singapore: World Scientific, 2006.
26. Alexander, G.J. Portfolio Performance Evaluation Using Value at Risk / G.J. Alexander, A.M. Baptista // The Journal of Portfolio Management Summer. - 2003. - V. 29, № 4. - P. 93-102.
27. Ignatov, A.N. On the Construction of Positional Control in a Multistep Portfolio Optimization Problem with Probabilistic Criterion / A.N. Ignatov // Automation and Remote Control. - 2020. - V. 81, № 12. - P. 2181-2193.
28. SolversMILP. - URL: https://github.com/al-ignatov/SolversMILP_comparison (дата обращения 02.05.2024)