Hybrid methods of solving non-numerical constraint satisfaction problems using specialized tables

Abstract

To increase the efficiency of representation and processing of qualitative domain dependencies within the framework of constraint programming technology, the article proposes to use specialized table structures: C- and D-systems. From the point of view of constraint programming technologies, these structures can be assigned to such a class of global constraints as compressed tables. For the first time, hybrid methods have been developed for solving problems of satisfaction of non-numerical constraints formalised with the help of the proposed C- and D-systems. A distinctive feature of the author’s methods is that they do not use depth-first search strategies, which lead to an exponential increase in the execution time of the computational procedures with an increase in the dimension of the problem. The first of the proposed hybrid methods integrates the author’s methods for non-numerical propagation of constraints with existing algorithms for the structural decomposition of the constraint graph. As a result of decomposition, the problem is divided into sub-problems, the constraint graph of each of which is a tree. In this case, the sub-problems are solved in polynomial time using the author’s algorithms for the propagation of non-numeric constraints. The method is well suited for situations where there is a series of problems with the same structure of the constraint graph, for example, when analysing typical queries for data warehouses. The second of the developed hybrid methods integrates the following components: original methods of non-numeric constraints propagation to reduce the dimension of the search space; a method of local search on partial assignments to quickly exit non-solution subspaces; a tabu search to avoid repeated passage of already investigated states. It is intended for situations when you need to find a solution based on a large amount of information, but there is no a priori information about the graph structure of the constraint satisfaction problem.