ABSTRACTS OF ARTICLES OF THE JOURNAL "INFORMATION TECHNOLOGIES".
No. 5. Vol. 30. 2024

DOI: 10.17587/it.30.240-251

Yu. A. Mezentsev, Dr. of Tech. Sc., Professor,
Novosibirsk State Technical University, Novosibirsk, Russian Federation

Heuristic Procedures for the Synthesis of Cutting Hyperplanes in Iterative Algorithms for Solving Mixed Linear Programming with Boolean Variables Problems

The main provisions for one of the promising directions of methods development of mixed integer linear programming are presented. The method is based on an iterative application of a cutting-plane procedure that takes into account, as fully as possible, the properties of the problems being solved. Heuristic procedures are applied for the synthesis of cutting-planes as an intermediate step substantiating the construction of a solution tree. The properties of the generated algorithms are experimentally investigated, the prospects and ways of developing the method and expanding the classes of discrete optimization problems to be solved are determined. The material is illustrated with simple visual examples.
Keywords: integer programming, binary cuts, efficient algorithm, binary cut-and branch algorithm, ant colony algorithm

P. 240-251

References

1. Leontiev V. K. Discrete optimization, Zhurnal vychislitel'noj matematiki i matematicheskoj fiziki. 2007, vol. 47, no. 2, pp. 338—352.
2. Available at: https://agora.guru.ru/display.php?conf=OPTIMA-2022, https://drive.google.com/file/d/1P_ VUCrv2gCHVR2GgSq7hgyvn29PpC6C1/view, http://motor2022.krc.karelia.ru/en/section/1, http://motor2023.uran.ru
3. Korte B., Vygen J. Combinatorial optimization. Theory and algorithms, Berlin, Heidelberg, New York, Barcelona, Lon­don, Milan, Paris, Springer, 2002, 572 p.
4. Du D., Pardalos P. (eds.) Handbook of combinatorial optimization. Supplement vol. A, Dordrecht, Boston, London, Kluwer academic publishers, 1999, 649 p.
5. Du D., Pardalos P. (eds.) Handbook of combinatorial optimization, Supplement vol. B, Boston, Springer, 2005, 403p.
6. Schrijver A. Theory of linear and integer programming, Chichester, New York, Wiley, 1999, 483 p.
7. Achterberg T. Constraint Integer Programming, Geneh-migte Dissertation doktor der Naturwissenschaften, Technischen Universitat Berlin, 2007,418 p.
8. IBM ILOG CPLEX V12.5 User's Manual for CPLEX. IBM Corporation, 2012, 952 p.
9. Zaslavsky A. A., Lebedev S. S. The method of nodal vectors of integer programming, Preprint # WP/2000/94, Moscow, CEMI RAN, 2000, 81 p.
10. Glover F., Kochenberger G. A. eds. Handbook of meta-heuristics, New York, Boston, Dordrecht, London, Kluwer academic publishers, 2003, 560 p.
11. Vasiliev I. L., Klimentova K. B. The method of branches and cuts for the problem of placement with customer preferences, Diskretnyj analiz i issledovanie operacij, 2009, vol. 16, no. 2, pp. 21—41.
12. Rutkovskaya D., Pilinsky M., Rutkovsky L. Neural networks, genetic algorithms and fuzzy systems, Moscow, Goryachaya liniya—Telekom, 2006, 452 p.
13. Mezentsev Yu. A. Efficient integer programming algorithm, Nauchnyj vestnik NGTU, 2009, no. 2(35), pp. 91—114.
14. Mezentsev Yu. A. Binary cut and branch method of integer programming, Doklady akademii nauk vysshej shkoly RF, 2011, no. 1(16), pp. 12—25.
15. Mezentsev Yu. A. Binary cut-and-branch method for solving linear programming problems with boolean variables, 2016 CEUR Workshop Proceedings, EID: 2-s2.0-85019596857, available at: http://ceur-ws.org/Vol-1623/paperco12.pdf.
16. Mezentsev Y. Binary cut-and-branch method for solving mixed integer programming problems, Constructive Nons-mooth Analysis and Related Topics (Dedicated to the Memory of V. F. Demyanov), CNSA 2017, available at: https://doi.org/10.1109/cnsa.2017.7973989
17. Brucker P. Scheduling Algorithms (Fifth ed.), Berlin, Boston, New York, Springer, 2007, 372 p.
18. Pinedo M. Scheduling Theory, Algorithms, and Systems (3nd. ed.), Berlin, Heidelberg, New York, Springer, 2008, 672 p.
19. Kaabi J., Harrath Y. A Survey of Parallel Machine Scheduling under Availability Constraints, International Journal of Computer and Information Technology, 2014, vol. 03, iss. 02, pp. 238—245.
20. Lin Y. K., Hsieh H. T., Hsieh F. Y. Unrelated Parallel Machine Scheduling Problem Using an Ant Colony Optimization Approach, World Academy of Science, Engineering and Technology, 2012, vol. 6, pp. 1798—1803.
21. Mezentsev Y. A., Estraykh I. V. An optimal fleet assignment and flight scheduling problem for an airline company, 2018CEUR Workshop Proceedings, no. 2098, pp. 277—290, EID: 2-s2.0-85048025360, available at: https://ceur-ws.org/Vol-2098/paper24.pdf.
22. Mezentsev Yu. A., Korotkova Yu. L., Estraykh I. V. The task and tools of optimal regulation of airline fleet schedules, Informacionnye texnologii, 2020, vol. 26, no. 8, pp. 450—459, doi: 10.17587/it.26.450-459.
23. Mezentsev Y. A., Chubko N. Y. On one bicriterion discrete optimization problem and a hybrid ant colony algorithm for its approximate solution, Lecture Notes in Computer Science, 2021, vol. 12689 LNCS, pp. 289—300, available at: https://link.springer.com/chapter/10.1007%2F978-3-030-78743-1_26.
24. Mezentsev Yu. A., Korotkova Yu. L., Estraykh I. V. An effective algorithm for solving the applied task of optimizing schedules of a parallel-sequential system, Informacionnye texnologii, 2021, vol. 27, no. 12, pp. 642—650, doi: 10.17587/it.27.642-650.
25. Mezentsev Y. A. Mathematical models of logistics subsystem management at enterprises, Avtomatizaciya i sovremenny'e texnologii, 2008, no. 8, pp. 46—55.
26. Mezentsev Y. A., Pavlov P. S. To the software implementation of a decomposition algorithm for solving one class of discrete optimization problems with semi-definite relaxation, Informacionnye texnologii, 2012. ¹ 2(186), pp. 54—59.
27. Baranova N. V., Mezentsev Y. A., Pavlov P. S. On the task and algorithms of coordinated optimal management of production and material flows of the enterprise, Sistemy' analiza i obrabotki dannyx. 2021, no. 3 (83), pp. 7—18, DOI: 10.17212/2782-20012021-3-7-18
28. Mezentsev Y. A., Razumnikova O. M., Tarasova I. V., Trubnikova O. A. On some tasks of clustering big data by minimax and additive criteria, application in medicine and neurophysiology, Informacionnye texnologii, 2019, vol. 25, no. 10, pp. 602—608, available at: https://doi.org/10.17587/it.25.602-608
29. Razumnikova O. M., Mezentsev Yu. A., Pavlov P. S., Tarasova I. V., Trubnikova O. A. Differentiation of cognitive status in patients with coronary artery disease using eeg clusterization by discrete optimization with a minimax criterion, Opera Medica et Physiologica, 2021, vol. 8, no. 3, pp. 42—51.

To the contents