Main Catalog Informatics, Computer Engineering and Control Information Technology. Computer techologies. Theory of computers and systems

Modern algorithms and digital tools for solving discrete optimization problems

Authors: Kiryukhin E.A.
Published in issue: #5(100)/2025
DOI:
Category: Informatics, Computer Engineering and Control \| Chapter: Information Technology. Computer techologies. Theory of computers and systems
Keywords: optimization problems, discrete optimization problems, traveling salesman problem, methods for solving optimization problems, population algorithm, Microsoft Excel add-in “Search for solutions”, C++ programming language
Published: 17.10.2025

The article presents an analysis of the formulation of discrete optimization problems and methods for their solution. The traveling salesman problem was considered as an example. To formulate its condition, a number of definitions and classifications were introduced, and then its mathematical model was constructed. Using the example of this task, we compared two common ways of solving optimization problems using modern digital tools. As the first method, a solution using the Microsoft Excel add-in “Solution Search” is considered. As a second solution, we considered the development of a software product that implements one of the methods for solving discrete optimization problems, namely, the evolutionary strategy of a population algorithm. This method was also used in the first solution method. It should be borne in mind that the software implementation of such a solution can be implemented in any modern programming language. The article provides an example of a software solution developed in the C++ programming language. Using the software developed, the solution identified both correct routes with the same minimum length for the specified source data, in contrast to the solution using the “Solution Search” add-on, which, due to the specifics of its organization, provided only one correct solution. Based on the results of comparing the two solutions, the expediency of solving optimization problems was substantiated by dividing the conditions of the task into input and output data, followed by the creation of a mathematical model of the problem, in particular, setting the objective function and developing a universal software solution in any modern programming language.

References

[1] Gashkov S.B. Discrete mathematics. St. Petersburg, Lan Publ., 2025, 520 p. (In Russ.).

[2] Shevlyakov A.N. Fundamentals of discrete mathematics. Omsk, OmSU Publ., 2020, 98 p. (In Russ.).

[3] Belousov A.I., Tkachev S.B. Discrete mathematics. Moscow, BMST Press, 2020, iss. 19, 703 p. (In Russ.).

[4] Rzhevsky S.V. Mathematical programming. Saint Petersburg, Lan Publ., 2022, 608 p. (In Russ.).

[5] Rogova N.V., Starozhilova O.V. Mathematical programming. Samara, PGUTI Publ., 2024, 177 p. (In Russ.).

[6] Boroznov V.O. Investigation of the solution of the traveling salesman problem. Bulletin of the Astrakhan State Technical University. Series: Management, Computer Engineering and Informatics, 2009, No. 2, pp. 147-151. (In Russ.).

[7] Rakhmangulov A.N., Tsyganov A.V., Pikalov V.A., Muravyev D.S. Mathematical modeling of transport systems and processes. Magnitogorsk, Magnitogorsk State Technical University Publ., 2021, 190 p. (In Russ.).

[8] Perlyuk V.V. Methods of optimization of design solutions. Saint Petersburg, GUAP Publ., 2023, 121 p. (In Russ.).

[9] Gapanovich V.S., Gapanovich I.V. Methods of solving optimization problems. Tyumen, TIU Publ., 2014, 272 p. (In Russ.).

[10] Searching for a solution in Excel: an example of using a function to solve a problem with unknown parameters. URL: https://exceltut.ru/poisk-resheniya-v-excel-primer-ispolzovaniya-funktsii-dlya-resheniya-zadachi-s-neizvestnymi-parametrami / (accessed 03/20/2025).

[11] Excel Solution Search function. Enabling, an example of use with screenshots. URL: https://office-guru.ru/excel/funkciya-poisk-resheniya-v-excel-vklyuchenie-primer-ispolzovaniya-so-skrinshotami.html (accessed 20.03.2025).