SOFTWARE SUBSYSTEM FOR SOLVING NP-COMPLEX COMBINATORIAL LOGIC PROBLEMS ON GRAPHS

Abstract

The paper is devoted to the development of the software for solving NP-hard and NP-hard
combinatorial-logical problems on graphs. The paper contains a description of graphs combinatorial-
logical problems. New multilevel search architectures such as simple combo, parallel combo,
two-levels, integrated, and hybrid are proposed to effectively address them. These architectures
are based on methods inspired by natural systems. The key difference between these architectures
is the division of search into two or three levels and the use of various algorithms for evolutionary
modeling and bioinspired search on them. This allows obtaining sets of quasi-optimal solutions to
perform parallel processing and partially eliminate the problem of premature convergence. The article
provides a detailed description of the developed software subsystem and its modules. As modules
in the subsystem, there are five developed architectures and a set of developed algorithms for evolutionary
modeling and bioinspired search, such as evolutionary, genetic, bee, ant, firefly and monkey.
Thanks to its modular structure, the subsystem has the ability to design more than 50 different search
combinations. This makes it possible to use all the advantages of bioinspired optimization methods
for efficiently solving NP-complex combinatorial-logical problems on graphs. To confirm the effectiveness
of the developed software subsystem, a computational experiment was carried out on test
examples. The series of tests and experiments carried out have shown the advantage of using a software
product for solving combinatorial-logical problems on graphs of large dimension, in comparison
with known algorithms, which indicates the prospects of using this approach. The time
complexity of the developed algorithms is O(nlogn)) at best, and O (n3) at worst.