МЕТОДЫ УДОВЛЕТВОРЕНИЯ ОГРАНИЧЕНИЙ ПРИ РЕШЕНИИ ЗАДАЧ КОМБИНАТОРНОГО ПОИСКА НА ПРИМЕРЕ ПЛАНИРОВАНИЯ ГОРНЫХ РАБОТ

Александр Анатольевич Зуенко; Юрий Андреевич Олейник

doi:10.17308/sait/1995-5499/2026/1/10-25

Authors

Alexander A. Zuenko Institute of Informatics and Mathematical Modeling – a separate subdivision of the Federal Research Center «Kola Science Center Russian Academy of Sciences»
Yuri A. Oleynik Institute of Informatics and Mathematical Modeling – a separate subdivision of the Federal Research Center «Kola Science Center Russian Academy of Sciences»

DOI:

https://doi.org/10.17308/sait/1995-5499/2026/1/10-25

Keywords:

constraint programming, constraint satisfaction problem, mining planning, medium-term planning, constraint propagation

Abstract

Discrete optimization problems that arise in industry are typically characterized by a large number of alternatives and strict requirements for computation time and RAM usage. In addition, the development of methods for solving such problems is complicated by the need to take into account and analyze additional domain-specific constraints that may arise during the process of iterative refining the customer’s requirements for the software being developed. Such tasks include, for example, scheduling for machinery and personnel at production. In these conditions, the use of specialized Operation Research methods, which are designed to effectively solve only relatively narrow subclasses of problems, is problematic. In turn, Artificial Intelligence methods allow for the coverage of broader classes of problems by unifying the representation of conditions and applying more general decision schemes, but at the same time, sometimes the efficiency of calculations is reduced. The article uses the Constraint Programming Paradigm as a methodological basis for developing intelligent methods for solving the problems under consideration. The application of this paradigm allows, on the one hand, to unify the processing of heterogeneous constraints, and, on the other hand, to design and reconfigure search procedures in order to increase their efficiency. The proposed approach is illustrated by the example of constructing a medium-term mining plan. The publication presents the formalization of the Mining Planning Problem as a Constraint Satisfaction Problem for the first time. The heuristics and methods of propagating specialized constraints that speed up the calculation process are analyzed in detail. The developed methods are implemented as a separate software library that is included in the MineFrame automated mining support system.

Author Biographies

Alexander A. Zuenko, Institute of Informatics and Mathematical Modeling – a separate subdivision of the Federal Research Center «Kola Science Center Russian Academy of Sciences»

PhD, leading researcher
Yuri A. Oleynik, Institute of Informatics and Mathematical Modeling – a separate subdivision of the Federal Research Center «Kola Science Center Russian Academy of Sciences»

researcher

References

1. Зуенко А. А. Интеграция концептуального моделирования и программирования в

ограничениях для синтеза схем технологических процессов / А. А. Зуенко, А. Г. Олейник, Ю. А. Олейник // Информационные технологии и вычислительные системы. – 2022. – № 3. – С. 95–107.

2. Зуенко А. А. Составление расписаний как задача удовлетворения ограничений (на примере планирования открытых горных работ) / А. А. Зуенко, Ю. А. Олейник // Информатика и автоматизация. – 2024. – № 23(5). – С. 1290–1310, doi: 10.15622/ia.23.5.1.

3. Basu A. Complexity of optimizing over the integers / A. Basu // Mathematical Programming. – 2023. – No 200. – P. 739–780. doi: 10.1007/s10107-022-01862-z.

4. Handbook of Constraint Programming / F. Rossi, P. Van Beek, P. Walsh editors. – Pisa : Italy. Elsevier, 2006.

5. Cappart Q. Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization / Q. Cappart, T. Moisan, L.-M. Rousseau, I. Prémont-Schwarz, A. A. Cire // AAAI Conference on Artificial Intelligence. (Vancouver, February 2-9 2021.). – Vancouver, 2021. – P. 3677–3687. doi: 10.1609/aaai.v35i5.16484

6. Çam Ö. N. The formulation of a linear programming model for the vehicle routing problem in order to minimize idle time / Ö. N. Çam, H. K. Sezen // Decision Making: Applications in Management and Engineering. – 2020. – № 3. – P. 22– 29. doi: 10.31181/dmame2003132h.

7. Rahman M. M. Automated Large-scale Class Scheduling in MiniZinc / M. M. Rahman, S. B. Noor, F. H. Siddiqui // The 2nd International Conference on Sustainable Technologies for Industry 4.0 (STI). (Dhaka, December 19-20 2020). – New York, 2020. P. 1–6. doi: 10.1109/ STI50764.2020.9350485.

8. Ek A. Modelling and Solving Online Optimisation Problems / A. Ek, M. G. de la Banda, A. Schutt, P. J. Stuckey, G. Tack // The AAAI Conference on Artificial Intelligence. (New York, February 7-12 2020.). – Palo Alto, 2020. – P. 1477– 1485. doi: 10.1609/aaai.v34i02.5506.

9. Nagovitsyn O. V. Development of mining and geological information system in the present-day situation in the Russian mining industry / O. V. Nagovitsyn // Russian Mining Industry. – 2023. – 6S. – P. 35–40. doi: 10.30686/1609-9192- 2023-6S-35-40.

10. Ghallab M. Automated Planning: Theory and Practice / M. Ghallab, D. Nau, P. Traverso – New York : Cambridge University Press, 2016. – 268 p.

11. Baptiste P. Constraint-based scheduling: applying constraint programming to scheduling problems / P. Baptiste, C. Le Pape, W. Nuijten. – New York: Springer, 2001. – 198 p. doi: 10.1007/978-1-4615-1479-4.

12. Зуенко А. А. Парадигма программирования в ограничениях при решении задач составления расписаний: аналитический обзор / А. А. Зуенко, О. В. Фридман, О. Н. Зуенко // Вестник ВГУ. Серия: Системный анализ и информационные технологии. – 2022. – № 4. – С. 156–179.

13. Nickel S. Decision Optimization with IBM ILOG CPLEX Optimization Studio / S. Nickel, C. Steinhardt, H. Schlenker, W. Burkart // A Hands-On Introduction to Modeling with the Optimization Programming Language (OPL). – Berlin, Heidelberg: Springer, 2022. – P. 9–21. doi: 10.1007/978-3-662-65481-1.

14. Schulte C. Modeling and Programming with Gecode / C. Schulte, G. Tack, M. Z. Lagerkvist. 2019. – 556 p.

15. Yarmuch J. L. Optimum ramp design in open pit mines / J. L.Yarmuch, M. Brazil, H. Rubinstein, D. A. Thomas // Computers and Operations Research. – 2020. – № 115. doi: 10.1016/j. cor.2019.06.013.

16. Paithankar A. Open pit mine production schedule optimization using a hybrid of maximum-flow and genetic algorithms / A. Paithankar, S. Chatterjee // Applied Soft Computing. – 2019. – № 81. doi: 10.1016/j.asoc.2019.105507.

17. Manriquez F. Short-term open-pit production scheduling optimizing multiple objectives accounting for shovel allocation in stockpiles / F. Manriquez, H. Gonzalez, N. Morales // Optimization and Engineering. – 2022. – № 24. – P. 681–707. doi: 10. 1007/ s11081-021- 09701-4.

18. Astrand M. Underground mine scheduling of mobile machines using Constraint Programming and Large Neighborhood Search / M. Astrand, M. Johansson, A. Zanarini // Computers & Operations Research. – 2020. – № 123. doi: 10.1016/j.cor.2020.105036.

19. Nadel A. Chronological Backtracking / A. Nadel, V. Ryvchin // Theory and Applications of Satisfiability Testing – SAT 2018. (Oxford, July 9–12 2018). – Cham, Springer. 2018. P. 111–121. doi: 10.1007/978-3-319-94144-8_7.