Journal of Computer and System Sciences InternationalJournal of Computer and System Sciences InternationalИзвестия Российской академии наук. Теория и системы управления0002-33883034-6444The Russian Academy of Sciences69920110.7868/S3034543X25060073COMPUTER METHODSКОМПЬЮТЕРНЫЕ МЕТОДЫResearch ArticleCONFIGURATION-ADAPTIVE PARALLEL SOLVER FOR INTEGER PROGRAMMING PROBLEMSКОНФИГУРАЦИОННО-АДАПТИВНЫЙ ПАРАЛЛЕЛЬНЫЙ РЕШАТЕЛЬ ДЛЯ ЗАДАЧ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯBezelM. A.БезельМ. А.mbezel@frccsc.ruGorchakovA. Yu.ГорчаковА. Ю.agorchakov@frccsc.ruKiyanchinD. S.КлянчинД. С.dklyanchin@frccsc.ruFederal Research Center "Computer Science and Control" of the Russian Academy of Sciences (FRCCSC RAS)Федеральный исследовательский центр «Информатика и управление» Российской академии наук (ФИЦ ИУ РАН)151220256NO6 (2025)№6 (2025)808723122025Copyright ©; 2025, Russian Academy of SciencesCopyright ©; 2025, Российская академия наук2025Russian Academy of SciencesРоссийская академия наукhttps://rjsvd.com/0002-3388/article/view/699201

This paper presents a parallel application software package for solving integer linear programming problems. The software is developed using a Master–Worker architecture and is intended for distributed-memory systems. A key feature of the package is a configuration-oriented approach to the branch-and-cut method. Each worker process that solves a part of a single branching tree is assigned a configuration that defines a set of parameters: the cut-generation method, the branching-variable selection strategy, the order of traversing the search tree, and the presence or absence of reductions. A subset of workers is allocated to evaluate the effectiveness of existing configurations and to compile their ranking. Test results demonstrate solution scalability. A comparative analysis with similar open-source solutions is provided.

Рассматривается пакет параллельного прикладного программного обеспечения для решения задач целочисленного линейного программирования. Программное обеспечение разработано с использованием архитектуры Мастер–Работник и предназначено для вычислительных систем с распределенной памятью. Ключевой особенностью разработанного пакета является конфигурационноориентированный подход к методу ветвей и отсечений. Каждому процессу-работнику, решающему часть одного дерева ветвлений, выдается конфигурация, определяющая набор параметров: метод генерации отсечений, стратегия выбора переменных ветвления, порядок обхода дерева ветвлений, наличие или отсутствие редукции. Часть работников отведена для исследования эффективности существующих конфигураций и составления их рейтинга. Результаты тестирования показывают масштабируемость решения. Проведен сравнительный анализ с аналогичными решениями, имеющими открытый исходный код.

configuration-oriented approachbranch-and-cut methodinteger linear programmingКонфигурационно-ориентированный подходметод ветвей и отсеченийцелочисленное линейное программированиеThis work was supported by the Ministry of Science and Higher Education of the Russian Federation (project No. 075-15-2024-544).Работа выполнена при финансовой поддержке Минобрнауки РФ (проект № 075-15-2024-544).Achterberg T. Constraint Integer Programming : diss. Technical University of Berlin, Berlin, 2007.Wolsey L. A. Integer Programming. Hoboken, USA. John Wiley & Sons, 2020.Smith D. R. Applications of a Strategy for Designing Divide-and-conquer Algorithms //Science of Computer Programming. 1987. V. 8. № 3. P. 213–229.Nowak A., Folque D., Bruna J. Divide and Conquer Networks //6th Intern. Conf. on Learning Representations. Vancouver, Canada, 2018.Goycoolea M. Cutting Planes for Large Mixed Integer Programming Models: Diss. The H. Milton Stewart School of Industrial & Systems Engineering. Atlanta, USA, 2006.Contardo C., Lodi A., Tramontani A. Cutting Planes from the Branch-and-bound Tree: Challenges and Opportunities // INFORMS J. on Computing. 2023. V. 35. № 1. P. 2–4.Berthold T. Primal MINLP Heuristics in a Nutshell //Intern. Conf. on Operations Research. Rotterdam: Shpringer, 2013.Berthold T. Primal Heuristics for Mixed Integer Programs : Diss. Technical University of Berlin, Berlin, 2006.Fischetti M., Lodi A. Primal Heuristics in Mixed Integer Programming //Wiley Encyclopedia of Operations Research and Management Science. Wiley. John Wiley & Sons, 2010.Fischetti M., Glover F., Lodi A. The Feasibility Pump //Mathematical Programming. 2005. V. 104. № 1. P. 91–104.Naoum-Sawaya J. Recursive Central Rounding for Mixed Integer Programs //Computers & Operations Research. 2014. V. 43. P. 191–200.Danna E., Rothberg E., Pape C.L. Exploring Relaxation Induced Neighborhoods to Improve MIP Solutions //Mathematical Programming. 2005. V. 102. № 1. P. 71–90.Berthold T. RENS: the Optimal Rounding //Mathematical Programming Computation. 2014. V. 6. № 1. P. 33–54.Dantzig G.B. Origins of the Simplex Method //A History of Scientific Computing. N.Y. USA: ACM, 1990.Bixby R.E. Implementing the Simplex Method: The Initial Basis //ORSA J. on Computing. 1992. V. 4. № 3. P. 267–284.Shamir R. The Efficiency of the Simplex Method: a Survey //Management science. 1987. V. 33. № 3. P. 301–334.Koberstein A. The Dual Simplex Method, Techniques for a Fast and Stable Implementation : Diss. Germany, Paderborn University, 2005.Potra FA., Wright S.J. Interior-point Methods // J. of Computational and Applied Mathematics. 2000. V. 124. № 1–2. P. 281–302.Gondolo J. Interior Point Methods 25 Years Later //European J. of Operational Research. 2012. V. 218. № 3. P. 587–601.Ralphs T., Shinano Y., Berthold T., Koch T. Parallel Solvers for Mixed Integer Linear Optimization //Handbook of Parallel Constraint Reasoning. Palaiseau, France: Springer, 2018.Mitchell J.E. Branch-and-cut Algorithms for Combinatorial Optimization Problems //Handbook of Applied Optimization. 2002. V. 1. № 1. P. 65–77.Achterberg T., Bixby R.E., Gu Z., Rothberg E., Weninger D. Presolve Reductions in Mixed Integer Programming // INFORMS J. on Computing. 2020. V. 32. № 2. P. 473–506.Hosten S., Thomas R.R. Gomory Integer Programs //Mathematical Programming. 2003. V. 96. № 2. P. 271–292.Snir M., Otto S., Huss-Lederman S., Walker D., Dongarra J. MPI — The Complete Reference. 2nd ed. Cambridge: MIT Press, 1998.Gropp W., Lusk E., Skjellum A. Using MPI: Portable Parallel Programming with the Message-passing Interface. Massachusetts: MIT press, 1999.Gleixner A., Hendel G., Gamrath G., Achterberg T., Bastubbe M., Berthold T., Shinano Y. MIPLIB 2017: Data-driven Compilation of the 6th Mixed-integer Programming Library //Mathematical Programming Computation. 2021. V. 13. № 3. P. 443–490.Xu Y., Ralphs T.K., Ladányi L., Saltzman M.J. Computational Experience With a Software Framework for Parallel Integer Programming //INFORMS J. on Computing. 2009. V. 21. № 3. P. 383–397.