Control Systems and Computers

https://doi.org/10.15407/csc.2022.01.015

Control Systems and Computers, 2022, Issue 1 (297), pp. 15-23.

UDC 004.93’1:519.157 

M.I. Schlesinger, doctor of science, professor, chief researcher,
International Research and Training Center for Information Technologies
and Systems NAS and MES of Ukraine, Glushkov ave., 40, Kyiv, 03187, Ukraine, schles@irtc.org.ua

SOLUTION OF SOFT CONSTRAINS PROBLEMS
VIA THEIR REPARAMETRIZATION

Introduction. The past quarter-century is characterized by the birth of a new scientific direction, formed as a result of combining research in pattern recognition problems and constraint satisfaction problems. These two scientific directions traditionally belong to the problem of artificial intelligence, but they formalize different aspects of intellectual activity. The formation of a single formal scheme that combines these two directions expands and concretizes the concept of machine thinking, on the formalization of which they are oriented, and necessitates the development of new and improvement of known mathematical optimization methods.

Objective. Comparison of three currently known polynomially solvable subclasses of the NP-hard class of optimization problems, which constitutes a mathematical formalization of a new scientific direction. Problems of the first subclass are solved by dynamic programming methods, problems of the second subclass are solved by supermodular maximization methods, and problems of the third subclass are solved by methods of equivalent transformation of optimization problems, also known as their reparametrization.

Result. The subclass of problems solved on the basis of their reparametrization includes subclasses solved using dynamic programming or supermodular maximization, and thus is the most extensive among the three currently known polynomially solvable subclasses.

Conclusion. Key moments in the process of formation of a new scientific direction are given.

Keywords: pattern recognition, constraint satisfaction, dynamic programming, supermodular maximization, reparametrization of
optimization problems.

 Download full text! (On Ukrainian)

1. Grytsenko I., Shlezynher M. Y., 2011. “Formalnye modely, zadachy y alhorytmy obraznoho myshlenyya”, Proceedings of the 18th International Conference on Automatic Control AUTOMATICS-2011 (Lviv, 28-30 Sept. 2011), pp. 110–113.
2. Grytsenko I., Shlezynher M. I., 2020. “Vzaimosvyaz problem raspoznavaniya obrazov, mashinnogo myshleniya i obucheniya”, International scientific and technical journal “Problemy upravleniya i informatiki”, 3, pp. 108–136.
3. Shlezynher, Hlavach V., 2004. Desyat lektsyy po statystycheskomu y strukturnomu raspoznavanyyu, Naukova dumka, Kyiv, 545 p.
4. Rossi, van Beek P., Walsh T., 2006. Handbook of Constraint Programming, Elsevier, 975 p.
5. Shlezynher I., 1976. “Sintaksicheskiy analiz dvumernykh zritelnykh signalov v usloviyakh pomekh”, Kibernetika, 4, pp. 113–129.
6. Shlezynher I., 1989. Matematicheskiye sredstva obrabotki izobrazheniy, Naukova dumka, Kyiv, 197 p.
7. Vintsyuk K., 1987. Analiz, raspoznavaniye i interpretatsiya rechevykh signalov, Naukova dumka, Kyiv, 262 p.
8. Kovalevskiy A., 1976. Metody optimalnykh resheniy v raspoznavanii izobrazheniy, Nauka, Moscow, 328 p.
9. Gimelfarb, G.L., 1979. “Symmetrical approach to the problem of automating stereoscopic measurements in photogrammetry”, Cybernetics and System Analysis, 15, pp. 235-247.
   https://doi.org/10.1007/BF01069335
10. Ishikawa H., Geiger D., “Segmentation by grouping junctions”, IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. 125–131.
11. Kovtun V., 2004. Sehmentatsiya zobrazhen na osnovi dostatnikh umov optymalnosti v NP-povnykh klasakh zadach strukturnoyi rozmitky, Ph. D. Thesis, International Research and Training Center for Information Technology and Systems, Kyiv.
12. Shlezynher I., Giginyak V. V., 2007. “Resheniye (max,+)-zadach strukturnogo raspoznavaniya pri pomoshchi ikh ekvivalentnykh preobrazovaniy”, Control systems and machines, Kyiv, 1, pp. 3–15, 2, pp. 3–18.
13. Energy Minimization Methods in Computer Vision and Pattern Recognition, EMMCVPR 2017, Lecture Notes in Computer Science, 10746, Springer.

Received 15.02.2022