Comparing the solvers for the mixed integer linear programming problems and the software environments that call them

Comparing the solvers for the mixed integer linear programming problems and the software environments that call them

Автор: Ignatov A.N., Ivanov S.V.

Журнал: Вестник Южно-Уральского государственного университета. Серия: Математическое моделирование и программирование @vestnik-susu-mmp

Рубрика: Программирование

Статья в выпуске: 3 т.17, 2024 года.

Бесплатный доступ

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.

Еще

Mixed integer linear programming, solver, comparison, software environment

Короткий адрес: https://sciup.org/147245968

IDR: 147245968   |   DOI: 10.14529/mmp240305

Список литературы Comparing the solvers for the mixed integer linear programming problems and the software environments that call them

  • Игнатов, А.Н. О задаче составления расписания грузоперевозок на участке железнодорожной сети и алгоритмах ее решения / А.Н. Игнатов // Вестник ЮУрГУ. Серия: Математическое моделирование и программирование. - 2021. - Т. 14, № 3. - С. 61-76.
  • 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.
  • 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.
  • Игнатов, А.Н. О выборе времени для установления «технологического окна > на железнодорожной станции / А.Н. Игнатов, А.В. Наумов // Вестник ЮУрГУ. Серия: Математическое моделирование и программирование. - 2019. - Т. 12, № 3. - С. 5-16.
  • 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.
  • 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.
  • Xiao, Yang. 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.
  • 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.
  • 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.
  • Иванов, С.В. Двухэтапная стохастическая модель размещения предприятий с квантиль-ным критерием и выбором уровня надежности / С.В. Иванов, В.Н. Акмаева // Вестник ЮУрГУ. Серия: Математическое моделирование и программирование. - 2021. - V. 14, № 3. - P. 5-17.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • Игнатов, А.Н. О решении задачи корректирования скалярного терминального состояния летательного аппарата при произвольном распределении мультипликативного возмущения / А.Н. Игнатов // Труды МАИ. - 2016. - № 87. - 19 c.
  • 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.
  • 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.
  • Borisov, A. Stochastic Time Complexity Surfaces of Computing Node / A. Borisov, A. Ivanov // Mathematics. - 2023. - V. 20, № 11. - P. 43-79.
  • 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.
  • Ziemba, W.T. Stochastic Optimization Models in Finance / W.T. Ziemba, R.G. Wickson. -Singapore: World Scientific, 2006.
  • 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.
  • 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.
  • SolversMILP. - URL: https://github.com/al-ignatov/SolversMILP_comparison (дата обращения 02.05.2024)
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp