Hybrid Search Methods Based on Table Representation of Non-quantitative Constraints Satisfaction Problems Alexander Zuenkoa a Institute for Informatics and Mathematical Modeling, Subdivision of the Federal Research Centre β€œKola Science Centre of the Russian Academy of Sciences”, Apatity, Russia Abstract The paper presents two forms of compressed table constraint representation: the 𝐢- and 𝐷-systems. The hybrid methods have been developed to solve non-quantitative constraint satisfaction problems formalized by table structures introduced. To make search more effective under the increase of the solution space, the hybrid methods integrate the original methods, such as non-quantitative constraint propagation and local search, as well as structural constraint graph decomposition methods. 1. Introduction In constraint programming, the generally accepted search methodology is based on a joint application of constraint propagation methods and backtracking methods. In so doing, use is made of both specialized heuristics in selection of the variable and its value, and intelligent strategies of backtracking to the state that caused the illegal assignment. The peculiarity of backtracking methods is that these methods allow step-by-step extension of a partial allowable solution to a complete one. If a partial solution turns out to be illegal, there is backtracking and the previous partial solution is extended to an alternative direction. In many practical applications related to processing of a large body of information, methods based on the search tree studies only, are not sufficiently effective compared to the local search methods which have been put to the fore now, as well as the hybrid methods combining the advantages of several search schemes [Blu11, Fei18, Nat15, Lim12, Jeg17]. A very important type of so-called global constraints in constraint programming technolo- gies is table constraints. A table form is very suitable for different non-numerical (qualitative) relations of the subject domain to be described. However, an increase in the size of the tables leads to an exponential increase in the complexity of the procedures used in tables processing. In this connection, of special actuality for table constraints are the development of the ways to compactly represent these in the computer memory, and the development of effective methods Russian Advances in Artificial Intelligence: selected contributions to the Russian Conference on Artificial intelligence (RCAI 2020), October 10-16, 2020, Moscow, Russia " zuenko@iimm.ru (A. Zuenko)  Β© 2020 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org) of their processing. There is a wide spectrum of studies dealing with compact representation of table constraints in the literature [Che10, Kat07, Ver17, Wan16]. Some studies deal with the constraint satisfac- tion algorithms presented by compressed tables [Che10]. The present paper is a study extend- ing a series of the author’s publications dealing with the properties of compressed tables and the development of methods of inference on compressed tables [Zue14, Zue17, Zue18a, Zue18b]. In order to make the representation and processing of table constraints more effective, the present study suggests two types of compressed tables: 𝐢-system and 𝐷-system. No work prototypes dealing with applications of the structures similar to 𝐷-systems in solving the con- straint satisfaction problems have been found by the author. An effective search in large-size compressed tables was first organized by specially devel- oped hybrid methods that integrate new methods of local search, non-quantitative constraint propagation, systematic search, as well as widely used methods of structural constraint graph decomposition. All the methods developed are based on a detailed analysis of the internal structure of the table constraint types proposed. The hybrid methods developed within the approach proposed are classified into two cate- gories: 1) the methods realizing the structural constraint graph decomposition in conjunction with constraint propagation; 2) the methods realizing constraints propagation in conjunction with local search. 2. Compressed representation of table constraints For it to be solved by the constraint programming technology, any applied problem should be represented as a constraint satisfaction problem. According to [Rus10], the Constraint Satisfaction Problem (CSP) consists of three compo- nents: <𝑋 , 𝐷, 𝐢>. 𝑋 – is a set of variables {𝑋1 , 𝑋2 , ..., 𝑋𝑛 }. 𝐷 – is a set of domains {𝐷1 , 𝐷2 , ..., 𝐷𝑛 }, where 𝐷𝑖 – is a variable domain 𝑋𝑖 . 𝐢 – is a set of constraints {𝐢1 , 𝐢2 , ..., πΆπ‘š }, which specify the allowed combinations of variable values. Each domain 𝐷𝑖 defines a set of a values {𝑣1 , ..., π‘£π‘˜ } for variable 𝑋𝑖 . Each constraint is a couple <π‘ π‘π‘œπ‘π‘’, π‘Ÿπ‘’π‘™>, where π‘ π‘π‘œπ‘π‘’ – is a set of variables taking part in the constraint, π‘Ÿπ‘’π‘™ – is a relation specifying the allowed combinations of values which can be taken by the variables from π‘ π‘π‘œπ‘π‘’. The assignment which does not violate any constraint, is called a legal assignment. A com- plete assignment is that in which every variable participates. The solution of the CSP is a complete assignment satisfying all the constraints. The constraints can be represented either by explicit enumeration of all the allowed combi- nations of values for the stated set of variables (an extensional way of specifying) or in a kind of an abstract relation supporting two operations, such as to test if a tuple is an element of the relation given, and to enumerate all the elements of the relation (an intentional way of specify- ing). Tables in relational databases can be an example of extensional relations. These relations play a very important role in the fields of CAD (computer aided design systems) and GIS (ge- ographic information systems). The constraint satisfaction algorithms supporting extensional relations (table constraints) are widely applied in the fields mentioned above. Speaking about intentional relations we mean the relations specified parametrically. These are practically all the relations over quantitative (continuous) domains. Very often, 𝑛-ary relations specified extensionally, can be represented more compactly if compared to a full enumerating of their tuples. Brought to attention is a mathematical apparatus for a "compressed" representation of 𝑛-ary relations, which uses two types of matrix-like structures. The first type is the 𝐢-systems. The 𝐢-system is a compressed table in which sets rather than separate elements act as cells. Let’s consider an example. Let there be the following relation: {(𝑐, 1), (𝑐, 2), (𝑐, 4), (𝑐, 5), (𝑏, 2), (𝑏, 4), (𝑑, 1), (𝑑, 5)} on variables 𝑋 , π‘Œ with domains: 𝑋 – {π‘Ž, 𝑏, 𝑐, 𝑑}, π‘Œ – {1, 2, 3, 4, 5}. Presented below are a 𝐢-system, which compactly describes the relation, and an algebraic expression over sets that corresponds to a given 𝐢-system: ⎑ {𝑐} {1, 2, 4, 5} ⎀ 𝑇 [𝑋 π‘Œ ] = ⎒ {𝑏} {2, 4} βŽ₯ = {𝑐} Γ— {1, 2, 4, 5} βˆͺ {𝑏} Γ— {2, 4} βˆͺ {𝑑} Γ— {1, 5}. ⎒ βŽ₯ ⎣ {𝑑} {1, 5} ⎦ Graphically, each row of the 𝐢-system corresponds to a subspace in the attribute space (Cartesian products of sets) and the whole 𝐢-system is a union of these subspaces. The other type of compressed tables, which provides a compact representation of 𝑛-ary rela- tions, is the 𝐷-system. This matrix is represented in reversed direct brackets. Given below is the 𝐷-system 𝑃[𝑋 π‘Œ ], which is equivalent to the 𝐢-system 𝑇 [𝑋 π‘Œ ] because both systems describe the same initial relation: ⎀ {𝑐, 𝑑} {2, 4} ⎑ 𝑃[𝑋 π‘Œ ] = βŽ₯ {𝑏, 𝑐} {1, 5} ⎒ = ({𝑐, 𝑑} Γ— {1, 2, 3, 4, 5} βˆͺ {π‘Ž, 𝑏, 𝑐, 𝑑} Γ— {2, 4}) ∩ βŽ₯ ⎒ ⎦ βˆ… {1, 2, 4, 5} ⎣ ∩({𝑏, 𝑐} Γ— {1, 2, 3, 4, 5} βˆͺ {π‘Ž, 𝑏, 𝑐, 𝑑} Γ— {1, 5}) ∩ ({π‘Ž, 𝑏, 𝑐, 𝑑} Γ— {1, 2, 4, 5}). The 𝐷-system is a complex algebraic expression. Each row of the 𝐷-system is a subspace in the attribute space, which is more complicated in structure than the Cartesian product of sets. Each row of the 𝐷-system is a union of definite Cartesian products. The 𝐷-system specifies the intersection of subspaces correlated to each of its rows. An empty component ("βˆ…" in the description of 𝐢- and 𝐷-systems) is a dummy component that does not contain values. Another dummy component is the full component – "βˆ—" – a designation for the entire range of possible values (domain) of an attribute. As in the case of conventional tables, relational algebra operations can be applied to the 𝐢- and 𝐷-systems. These operations are implemented without decomposition of the 𝐢- and 𝐷-systems into conventional tables, using specialized theorems. In addition, the operation of complement of 𝑛-ary relations is widely applied to the 𝐢- and 𝐷-systems, which in fact is not used in the relational databases. More details about operations with 𝐢- and 𝐷-systems can be found in [Kul15]. Represented here is the theorem which is to be used in the presentation below. Theorem 1. The result of join of two 𝐢-systems can be presented as a 𝐢-system composed of rows produced from joining of each vector-row of the first 𝐢-system with each vector-row of the second 𝐢-system. Now, change to the description of the hybrid search methods for the proposed types of com- pressed tables. 3. Structural decomposition of the constraint graph and constraint propagation We have developed hybrid method that integrates the author’s methods of non-quantitative constraints propagation [Zue17, Zue18a] and the known methods of structural decomposition of the constraint graph [Dec89, Mig01]. It is known that if the graph of the constraint satisfac- tion problem (sub-problem) has a tree structure, then, in order to reach its solution, it is enough to apply only the constraint propagation methods. The peculiarity of the method developed is in that a set of solutions of each sub-problem are being reached in a form of a 𝐢-system, i.e., sub-spaces are being found in the space of legal assignments per algorithm step, which substantially reduces the time necessary to carry out computational procedures. The method proposed consists of three basic stages: 1. The graph of constraints of the initial problem is partitioned into loosely-coupled or independent sub-problems, the graphs of constraints of which are trees. At this stage well known methods of structural decomposition of the constraint graph are applied (for instance, the tree decomposition or cycle cutset methods). 2. Each sub-problem is solved by the well known algorithm applied in solving the con- straint satisfaction problem with a tree structure and by the author’s methods of non- quantitative constraint propagation. The solution of each sub-problem is being reached in a form of the 𝐢-system. 3. Based on Theorem 1, the sub-problems solution are joined into a solution of a common problem defined also by the 𝐢-system. The representation of a set of solutions as the 𝐢-system substantially economizes the mem- ory resources and accelerates computational procedures in solution searching in comparison with explicit enumeration of all the possible solutions. At the same time, it is not difficult to explicitly enumerate all the elementary solutions on the basis of their representation in a form of the 𝐢-system because the 𝐢-system possesses a simple characteristic function. Thus, the method developed integrates two basic components: a) the component realizing the algorithms of propagation; b) the component realizing the structural decomposition of the initial problem. Considered below are the principles of these two components functioning. 3.1. Structural decomposition algorithms Consider the basic approaches which the structural algorithms are based on. To put it another way, let’s define the ways allowing us to use the structure of the problem, which is represented as a constraint graph, to accelerate the search of the solution. The structure or the topology of CSPs can be defined by different graph structures: (primary) constraint graph, constraint hypergraph, dual constraint graph. The primal constraint graph of the CSP (𝑉 , 𝐷, 𝐢) – is a non-oriented graph 𝐺 = (𝑉 , 𝐸), the nodes 𝑉 of which correspond to the variables of the CSP, with two nodes being combined by the edge in graph 𝐺 if the corresponding variables participate in the same constraint. The primary graph will be taken as the constraint graph hereinafter the paper. The constraint graph can be used to partition the problem into a complex of simpler, in terms of computational complexity, sub-problems. If the CSP composition allows us to distinguish sub-problems fully independent of each other, it is possible to solve these separately, and the solutions can be combined into a solution of the initial problem. To partition the CSPs into independent sub-problems, we can consider the connected com- ponents of the constraint graph. Suppose that each sub-problem of the CSP contains 𝑐 variables of the total number of variables (𝑛). In this case, the number of sub-problems is 𝑛/𝑐, and to solve each sub-problem, the volume of work is 𝑑 𝑐 , where 𝑑 is the size of the variables domain. Thus, the total volume of work is measured by the value 𝑂(𝑑 𝑐 Γ— 𝑛/𝑐), which linearly depends on 𝑛; if the decomposition were absent, the total volume of work would be measured by the value 𝑂(𝑑 𝑛 ), which exponentially depends on 𝑛. So, the totally independent sub-problems are very attractive. However these are rather rare. In most cases the sub-problems of any CSP are connected with each other by variables. In the simplest case, the constraint graph is a tree: any two variables are connected not more than by one way. The algorithms of a solution of a CSP having a tree structure, possess low computational complexity (CSP can be solved in linear time) [Mig01]. As there is an effective algorithm for trees, one should consider the question if there is any possible way to reduce more common constraint graphs to tree structures. There are two basic ways of solving this problem: one of these is based on eliminating the nodes, the other is based on merging the nodes with each other and on forming the super-nodes. The first approach envisages the assignment of values to some variables so that the variables left form a tree. The first approach is based on the well known methods, such as the cycle cutset method [Dec90] and the method of detecting the connected components of the constraint graph [Dec87, Fre82]. The typical methods implemented in the second approach include the method of tree decomposition [Dec89, Dec87, Fre85] and the method of tree-clustering [Dec89]. Structural decomposition methods are also effectively applied in solutions of CSPs that con- tain non-binary constraints, particularly, global constraints [Tho16]. The methods of structural decomposition mentioned above possess the following common features. Each sub-problem of a common CSP is solved independently: if any of these has no solution, the whole problem has no solution either. If all the sub-problems are solved, there is an attempt to reach a global solution. 3.2. Methods for propagation of constraints represented as 𝐢-systems Given below are the statements allowing realization of the equivalent transformations of the constraints for the case when constraints are represented as a set of the 𝐢-systems [Zue17]. The aim of the transformations is to bring the CSP to a simpler form, which contains a lesser number of the 𝐢-systems, rows of the 𝐢-systems, columns (attributes) of the 𝐢-systems, values in the attributes domains etc. Statement 1 (S1). If all the rows (tuples) of the 𝐢-system are empty, that is, each row contains at least one empty component, the 𝐢-system is empty (the corresponding CSP is inconsistent). Statement 2 (S2). If all the components of an attribute (a column of the 𝐢-system) are full, this attribute can be eliminated from the 𝐢-system (all the components in the corresponding column are eliminated), and a couple "the eliminated attribute – its domain" is preserved in the vector of the partial solution. Statement 3 (S3). If the domain of an attribute of the 𝐢-system contains values not occurred in the corresponding column, these values are eliminated from the given domain. Statement 4 (S4). If the row of the 𝐢-system contains at least one empty component (the row is empty), the row is eliminated. Statement 5 (S5). If the component of an attribute contains the value not belonging to the corresponding domain, this value is eliminated from the component. Statement 6 (S6). If one row of the 𝐢-system completely dominates (contains component- wise) the other row, the dominated row is eliminated from the 𝐢-system. A part of the statements makes it possible to eliminate the values from the domains and the components of the attributes (S3, S5) or the columns-attributes (S2), and a part of them makes it possible to eliminate extra rows (S4, S6) from consideration. The indicator of successful completion of searching is the elimination of all the rows and columns from the 𝐢-system, with no empty rows formed. To put it another way, in this case, the resulting state is characterized only by a complex of non-empty reduced domains in the tuple of the solution. The indicator of inconsistency of the CSP is the emptiness of the 𝐢-system (S1). The similar statements for the 𝐷-system are given below. 3.3. An example of the method realization Let the following correspondences "attribute – attribute domain" be specified: π΄βˆ’{π‘Ž1 ,π‘Ž2 ,π‘Ž3 ,π‘Ž4 ,π‘Ž5 ,π‘Ž6 }, 𝐡 βˆ’ {𝑏1 , 𝑏2 , 𝑏3 , 𝑏4 , 𝑏5 , 𝑏6 , 𝑏7 , 𝑏8 , 𝑏9 }, 𝐢 βˆ’ {𝑐1 , 𝑐2 , 𝑐3 , 𝑐4 , 𝑐5 , 𝑐6 }, 𝐷 βˆ’ {𝑑1 , 𝑑2 , 𝑑3 , 𝑑4 , 𝑑5 , 𝑑6 }, 𝐸 βˆ’ {𝑒1 , 𝑒2 , 𝑒3 , 𝑒4 , 𝑒5 , 𝑒6 , 𝑒7 , 𝑒8 }, 𝐹 βˆ’ {𝑓1 , 𝑓2 , 𝑓3 , 𝑓4 , 𝑓5 , 𝑓6 , 𝑓7 , 𝑓8 , 𝑓9 , 𝑓10 , 𝑓11 , 𝑓12 , 𝑓13 , 𝑓14 }. Also specified is the following set of constraints written in a form of the 𝐢-systems (their semantics is not essential in the example): πΆπ‘œπ‘›π‘ π‘‘π‘Ÿπ‘Žπ‘–π‘›π‘‘ 𝑅1 [𝐴𝐡] πΆπ‘œπ‘›π‘ π‘‘π‘Ÿπ‘Žπ‘–π‘›π‘‘ 𝑅2 [𝐡𝐢] πΆπ‘œπ‘›π‘ π‘‘π‘Ÿπ‘Žπ‘–π‘›π‘‘ 𝑅3 [𝐷𝐢] ⎑ {π‘Ž1 } {𝑏1 , 𝑏2 } ⎀ ⎑ {𝑏1 } {𝑐1 } ⎀ ⎑ {𝑑1 } {𝑐1 } ⎀ ⎒ {π‘Ž2 } {𝑏3 , 𝑏4 , 𝑏5 } βŽ₯ ⎒ {𝑏2 , 𝑏3 , 𝑏6 } {𝑐2 } βŽ₯ ⎒ {𝑑2 } {𝑐2 } βŽ₯ ⎒ βŽ₯ ⎒ βŽ₯ ⎒ βŽ₯ ⎒ {π‘Ž3 } {𝑏6 } βŽ₯ ⎒ {𝑏4 } {𝑐3 } βŽ₯ ⎒ {𝑑3 } {𝑐3 } βŽ₯ ⎒ {π‘Ž4 } {𝑏7 } βŽ₯ ⎒ {𝑏5 , 𝑏7 } {𝑐4 } βŽ₯ ⎒ {𝑑4 } {𝑐4 } βŽ₯ ⎒ {π‘Ž5 } {𝑏8 } βŽ₯ ⎒ {𝑏8 } {𝑐5 } βŽ₯ ⎒ {𝑑5 } {𝑐5 } βŽ₯ ⎒ βŽ₯ ⎒ βŽ₯ ⎒ βŽ₯ ⎣ {π‘Ž6 } {𝑏9 } ⎦ ⎣ {𝑏9 } {𝑐6 } ⎦ ⎣ {𝑑6 } {𝑐6 } ⎦ πΆπ‘œπ‘›π‘ π‘‘π‘Ÿπ‘Žπ‘–π‘›π‘‘ 𝑅6 [𝐹 𝐸] πΆπ‘œπ‘›π‘ π‘‘π‘Ÿπ‘Žπ‘–π‘›π‘‘ 𝑅5 [𝐢𝐹 ] ⎑ {𝑓1 , 𝑓6 } {𝑒1 } ⎀ πΆπ‘œπ‘›π‘ π‘‘π‘Ÿπ‘Žπ‘–π‘›π‘‘ 𝑅4 [𝐸𝐷] ⎒ {𝑓2 , 𝑓3 , 𝑓4 } {𝑒2 } βŽ₯ ⎑ {𝑒1 } {𝑑1 } ⎀ ⎑ {𝑐1 } {𝑓1 , 𝑓2 } ⎀ ⎒ βŽ₯ ⎒ {𝑒2 } {𝑑2 , 𝑑3 } βŽ₯ ⎒ {𝑐2 } {𝑓3 , 𝑓4 , 𝑓5 } βŽ₯ ⎒ {𝑓4 , 𝑓6 } {𝑒3 } βŽ₯ ⎒ βŽ₯ ⎒ βŽ₯ ⎒ {𝑓5 , 𝑓7 } ⎒ {𝑐3 } {𝑓6 , 𝑓7 } βŽ₯ {𝑒4 } βŽ₯ ⎒ {𝑒3 } {𝑑2 } βŽ₯ ⎒ {𝑐4 } {𝑓8 , 𝑓9 , 𝑓10 } βŽ₯ ⎒ {𝑓 , 𝑓 , 𝑓 } {𝑒 } βŽ₯ ⎒ {𝑒6 } {𝑑4 } βŽ₯ ⎒ {𝑐5 } {𝑓11 , 𝑓12 } βŽ₯ ⎒ 8 9 11 5 βŽ₯ ⎒ {𝑒 } {𝑑 , 𝑑 } βŽ₯ ⎒ βŽ₯ ⎒ {𝑓9 , 𝑓11 , 𝑓14 } {𝑒6 } βŽ₯ ⎣ 7 5 6 ⎦ ⎣ {𝑐6 } {𝑓13 , 𝑓14 } ⎦ ⎒ {𝑓10 , 𝑓13 } {𝑒7 } βŽ₯ ⎒ βŽ₯ ⎣ {𝑓12 , 𝑓14 } {𝑒8 } ⎦ The task is to calculate the join of the present relations, i.e., it is necessary to find: 𝑅1 [𝐴𝐡] β‹Š ⋉ 𝑅2 [𝐡𝐢] β‹Š ⋉ 𝑅3 [𝐷𝐢] β‹Š ⋉ 𝑅4 [𝐸𝐷] β‹Šβ‹‰ 𝑅5 [𝐢𝐹 ] β‹Šβ‹‰ 𝑅6 [𝐹 𝐸]. Figure 1 shows the graph of the CSP. Figure 2 shows an example of the structural decompo- sition of the graph of the initial CSP, which has been considered earlier (Figure 1). The initial CSP is partitioned into sub-problems by the assignment of the values to the variable 𝐢. Figure 1: The graph of the initial CSP Figure 2: The effect of the structural decomposition after the assignment of the values to the variable 𝐢 In this case, in order to solve the initial problem, it is necessary to consider two sub-problems: 1. 𝑅2 [𝐡𝐢] β‹Š ⋉ 𝑅1 [𝐴𝐡]; 2. 𝑅3 [𝐷𝐢] β‹Š ⋉ 𝑅4 [𝐸𝐷] β‹Šβ‹‰ 𝑅6 [𝐹 𝐸] β‹Š ⋉ 𝑅5 [𝐢𝐹 ]. It is possible, in advance, to calculate the corresponding multi-place relation for each sub- problem of the CSP, which results from the process of structural decomposition. Then, these relations can be joined into one. Let’s suppose that the value 𝑐1 is assigned to the variable 𝐢, then the domain of the variable 𝐢 becomes a singleton set {𝑐1 }. Let’s consider the first sub-problem of CSP (𝑅2 [𝐡𝐢] β‹Š ⋉ 𝑅1 [𝐴𝐡]). The graph of the sub-problem is a tree, hence, the solution of the sub-problem can be reached using only the methods of non- quantitative constraint propagation developed earlier, not using the backtracking methods. First, constraint 𝑅2 [𝐡𝐢] is activated and, based on Statements S1-S5, "tuned" to a new domain of variable 𝐢. After S5 being applied, all the rows, but the first one, of the initial 𝐢-system 𝑅2 [𝐡𝐢] are empty. Then, according to S4, constraint 𝑅2 [𝐡𝐢] takes the form of [{𝑏1 } {𝑐1 }]. Now, according to S3, we may conclude that a new domain of variable 𝐡 is singleton {𝑏1 }. Then constraint 𝑅1 [𝐴𝐡] is activated and, being "tuned" to a new domain of variable 𝐡, takes the form of [{π‘Ž1 } {𝑏1 }]. So, we have finished moving from constraint 𝑅2 [𝐡𝐢] to constraint 𝑅1 [𝐴𝐡] . The movement in the opposite direction can be represented as a result of "reduced" con- straints joining. We have the following vector-row in the scheme [𝐴𝐡𝐢]: [{π‘Ž1 } {𝑏1 } {𝑐1 }]. Now, we still think that variable 𝐢 takes the value 𝑐1 , and will consider the second sub- problem: 𝑅3 [𝐷𝐢] β‹Š ⋉ 𝑅4 [𝐸𝐷] β‹Š ⋉ 𝑅6 [𝐹 𝐸] β‹Š ⋉ 𝑅5 [𝐢𝐹 ]. Considering constraint 𝑅3 [𝐷𝐢] and taking into account a new domain of variable 𝐢, we conclude that the constraint is converted into vector-row [{𝑑1 } {𝑐1 }], and the domain of variable 𝐷 is reduced to a singleton set {𝑑1 }. Being activated, constraint 𝑅4 [𝐸𝐷], is converted into vector-row [{𝑒1 } {𝑑1 }], and the domain of variable 𝐸 is reduced to {𝑒1 }. After that constraint 𝑅6 [𝐹 𝐸] is analyzed, being reduced to vector-row [{𝑓1 , 𝑓6 } {𝑒1 }]. The domain of variable 𝐹 is reduced to {𝑓1 , 𝑓6 }. Finally, constraint 𝑅5 [𝐢𝐹 ] is activated, which, taking into account all the specified domains, is converted to vector-row [{𝑐1 } {𝑓1 }]. Moving the opposite direction results in a vector-row in the scheme [𝐢𝐷𝐸𝐹 ] ∢ [{𝑐1 } {𝑑1 } {𝑒1 } {𝑓1 , 𝑓6 }]. Thus, we have implemented an elementary algorithm step. All the rest steps for the five assignments left are made in the same way. The results of all the steps can be classified into two 𝐢-systems. 𝐴 𝐡 𝐢 1 ⎑ {π‘Ž1 } {𝑏1 } {𝑐1 } ⎀ ⎒ βŽ₯ 2 ⎒ {π‘Ž1 } {𝑏2 } {𝑐2 } βŽ₯ 𝐢 𝐷 𝐸 𝐹 3 ⎒ {π‘Ž2 } {𝑏3 } {𝑐2 } βŽ₯ 1 ⎑ {𝑐1 } {𝑑1 } {𝑒1 } {𝑓1 } ⎀ 4 ⎒ {π‘Ž3 } {𝑏6 } {𝑐2 } βŽ₯ 2 ⎒ {𝑐2 } {𝑑2 } {𝑒2 } {𝑓3 , 𝑓4 } βŽ₯ ⎒ βŽ₯ , ⎒ βŽ₯ 5 ⎒ {π‘Ž2 } {𝑏4 } {𝑐3 } βŽ₯ 3 ⎒ {𝑐2 } {𝑑2 } {𝑒3 } {𝑓4 } βŽ₯ 6 ⎒ {π‘Ž2 } {𝑏5 } {𝑐4 } βŽ₯ 4 ⎒ {𝑐4 } {𝑑4 } {𝑒6 } {𝑓9 } βŽ₯ 7 ⎒⎒ {π‘Ž4 } {𝑏7 } {𝑐4 } βŽ₯ βŽ₯ 5 ⎒⎣ {𝑐6 } {𝑑6 } {𝑒7 } {𝑓13 } βŽ₯ ⎦ 8 ⎒ {π‘Ž5 } {𝑏8 } {𝑐5 } βŽ₯ 9 ⎒ {π‘Ž6 } {𝑏9 } {𝑐6 } βŽ₯ ⎣ ⎦ Of all the 𝐢-systems represented, the first one (from left to right) describes a set of solutions for the first sub-problem of the CSP, the second one – for the second sub-problem of the CSP. Now the two 𝐢-systems can be joined (by the common variable 𝐢) to obtain the resulting 𝐢- system describing all the solutions of the initial problem. The two 𝐢-systems are being joined for polynomial time according to Theorem 1. Next, we consider the second of the developed hybrid methods. 4. Constraint propagation and local search Constraint propagation methods and local search methods are known to possess low compu- tational complexity. Due to it, of promising perspective is the integration of methods of these classes into hybrids. However, it is known that methods of constraint propagation use partial assignments (only some variables are instantiated) in order, based on specified values of some variables, to make conclusions about reducing the domains of the variables left, and methods of local search use complete assignments (all the variables take values) which either are taken as allowed or are modified in a special way to produce allowed assignments. The paper proposes a hybrid method integrating the following components: 1. the author’s methods of non-quantitative constraint propagation (methods of inference on the 𝐷-systems) to reduce the solution space; 2. the method of local search for partial assignments, which is based on application of heuristics with minimum conflicts for quick transition from elimination of sub-spaces containing no solution; 3. Tabu search [Ste97] to avoid repeated analyzing states already studied. 4.1. Inference on the 𝐷-systems We state, without proving, the statements used to organize inference on the 𝐷-systems [Zue14]: Statement 1’ (S1’). If at least one row of the 𝐷-system is empty (contains all the empty components), the 𝐷-system is empty (the corresponding system of constraints is inconsistent, the CSP has no solution). Statement 2’ (S2’). If all the components of an attribute are empty, the attribute can be elim- inated from the 𝐷-system (all the components in the corresponding column are eliminated). Statement 3’ (S3’). If in the 𝐷-system there is a row (tuple) containing exactly one non- empty component, all the values not included into the component, are eliminated from the corresponding domain. Statement 4’ (S4’). If a row of the 𝐷-system contains at least one full component, it is elimi- nated (the corresponding constraint can be eliminated from the constraint system). Statement 5’ (S5’). If a component of an attribute of the 𝐷-system contains a value not belonging to the corresponding domain, the value is eliminated from the component. Statements 1’-5’ allow elimination of all the "extra" values from some components, from do- mains of variables (attributes), elimination of rows and/or columns of the constraint matrices, reducing the search space and accelerating reaching the solution of the CSP. Based on the state- ments above, the well known arc and node consistency algorithms were modified for cases of non-quantitative constraints [Zue18a]. 4.2. Local search based on the analysis of compressed tables The local search methods are the basic methods used in solution of complex CSPs. The idea is to start the local search from choosing a randomly generated candidate in the solution of the problem (complete assignment) and improve it, step by step, for example, by reducing the number of unsatisfied constraints (conflicts). The local search algorithms differ in methods of finding this improvement. One of the disadvantages of local algorithms is their incompleteness, i.e. the search may stop at a local optimum, which in fact is not a global solution. The paper [Zue18b] presents an approach to organize the local search process for the solu- tion of the CSPs, which is based on a compressed representation of the qualitative constraints in a form of the 𝐷-systems and on an application of the statements about revealing the sub-spaces in the spaces legal and/or illegal assignments. In organizing the local search procedures on the 𝐷-systems, a notion of a conflict is inter- preted as follows: a conflict means a situation when in the process of assignment of the values to all the variables of the 𝐷-system there is an empty row formed in the 𝐷-system. An empty row is a row completely composed of empty components. In terms of the systematic search methods, the presence of at least one empty row means that the constraint is inconsistent and backtracking is necessary. As part of the proposed approach to organizing local search, it is necessary to calculate the number of the conflicts so that to make a decision about further progress to neighboring assignments. Now, let’s clarify a notion of a neighboring state. A neighboring state is a complete assign- ment which differs from the current one only in the value of one variable. The local search process is reduced to the change from the current state to the neighboring one until the constraint (𝐷-system) is satisfied or until the number of trials is exhausted. Of all the possible neighboring states, the one allowing to reach the solution by the fastest way, is chosen. To do that, it is recommended to apply the following heuristics. Of all the variables of the conflict set, it is recommended to choose a one which participates in the greatest quantity of conflicts. The variable is included into variables of the conflict set if the assignment in this attribute is one of the reasons of the formation of at least one empty row. It is recommended to choose the value the most often met in the corresponding column. The paper [Zue18b] also deals with the way of accelerating the local search methods on the compressed tables proposed. This acceleration is based on applying the consequences of the theorem presented below. The theorem is based on the partial order relations, which are determined for the values inside the domain of each attribute. So let’s first remind that, if in the 𝐷-system, with the scheme 𝑆 and a set of the numbers of tuples, one chooses an attribute 𝑋 (𝑋 is included into the scheme 𝑆) with the domain 𝐷𝑋 , then, for the values from 𝐷𝑋 , the partial order relation "≀" is introduced as follows: π‘Ž ≀ 𝑏, if and only if {π‘›π‘œ } βŠ† {𝑛𝑝 }, where: π‘Ž, 𝑏 ∈ 𝐷𝑋 ; and {π‘›π‘œ } and {𝑛𝑝 } are the sets of the numbers of the rows of the 𝐷-system whose components of the attribute 𝑋 contain the values π‘Ž and 𝑏, respectively. To put it another way, one value dominates the other within one domain if it occurs in the given column in all the rows where the first one is found, and in some other rows. Figure 3 shows the Hasse diagrams for the values of the attributes 𝑋 and π‘Œ of a 𝐷-system. Thus for the attribute π‘Œ the value 𝑔 dominates the value 𝑒 (i.e., 𝑔 β‰₯ 𝑒), as it, like 𝑒, is present in row 3 in the second column but is present in row 1 in the second column where 𝑒 is absent. As a whole, as for the attribute π‘Œ , we have 𝑒, 𝑓 , β„Ž ≀ 𝑔. For attribute 𝑋 ∢ 𝑑 ≀ π‘Ž, 𝑏. Theorem 2. If in the 𝐷-system with the scheme 𝑆 for an attribute 𝑋 (𝑋 belongs to the scheme 𝑆) with the domain 𝐷𝑋 there is: π‘Ž ≀ 𝑏, then for any couple of complete assignments {(𝑋1 , 𝑐1 ), ..., (π‘‹π‘βˆ’1 , π‘π‘βˆ’1 ), (𝑋𝑝 , π‘Ž), (𝑋𝑝+1 , 𝑐𝑝+1 ), ..., (𝑋𝑛 , 𝑐𝑛 )} and {(𝑋1 , 𝑐1 ), ..., (π‘‹π‘βˆ’1 , π‘π‘βˆ’1 ), (𝑋𝑝 , 𝑏), (𝑋𝑝+1 , 𝑐𝑝+1 ), ..., (𝑋𝑛 , 𝑐𝑛 )} the number of conflicts generated by the second assignment is not greater than that generated by the first assignment. Consequence 2.1. If a value 𝑏 of the attribute 𝑋𝑝 , belongs to the illegal assignment, then, in replacing the value 𝑏 to some other value π‘Ž, with the value π‘Ž ≀ 𝑏, we also obtain an illegal assignment. Consequence 2.2. If a value π‘Ž of the attribute 𝑋𝑝 , belongs to the legal assignment, then, in replacing the value π‘Ž to some other value 𝑏, with the value π‘Ž ≀ 𝑏, we also obtain a legal Figure 3: The partial order relation on the values of the attributes domains of the initial 𝐷-system assignment. Considered below are the typical cases when the theorem and the consequences mentioned above are capable to accelerate searching. Firstly, it is possible to generate the assignments containing dominating values in each at- tribute. Applied to our example, the following assignment: {(𝑋 , π‘Ž), (π‘Œ , 𝑔), (𝑍 , 𝑙)} is generated. It satisfies the 𝐷-system shown in Figure 3, so it is the solution. Secondly, if a solution is reached, then, based on the Consequence 2.2, it is possible to extend it to a sub-space in the legal assignments space. If the assignment {(𝑋 , π‘Ž), (π‘Œ , 𝑔), (𝑍 , 𝑙)} is the solution, then, taking into account the partial order relations in the variables domains, we obtain a sub-space of legal assignments 𝑋 βˆ’ {π‘Ž, 𝑏}, π‘Œ βˆ’ {𝑔}, 𝑍 βˆ’ {𝑖, π‘˜, 𝑙}. In particular, one of the solutions derived is {(𝑋 , 𝑏), (π‘Œ , 𝑔), (𝑍 , 𝑙)}. Thirdly, if there are conflicts in the current state, then, in changing to the neighboring state in the given conflict attribute, the priority should be given to one of the dominating values allowable at the stage of a choice. The heuristics proposed earlier and dictating to choose the values that are found in columns more often, is a peculiar approximation of the given rule. Finally, if an illegal assignment is found, it can be extended, based on Consequence 2.1, to an illegal assignments sub-space. Let an illegal assignment {(𝑋 , 𝑐), (π‘Œ , 𝑔), (𝑍 , 𝑙)} be found at the current stage, which generates a conflict in the second row. Then, taking into account the partial order relations in the variables domains, we have the following sub-space in the illegal assignment space: 𝑋 βˆ’ {𝑐}, π‘Œ βˆ’ {𝑒, 𝑓 , β„Ž, 𝑔}, 𝑍 βˆ’ {𝑖, π‘˜, 𝑙}. 4.3. The scheme of the hybrid method based on the local search The hybrid method developed is based on the constraint satisfaction problem representation as the 𝐷-system, using the conflict calculation heuristics to modify the current inconsistent partial assignment. It is suggested to model the assignment vector as the 𝐢-type vector-row whose components can contain not only a particular value but a set of allowed values of the given variable. At the stage of extending the current partial assignment, a variable with minimum domain is chosen, and then a choice is made of the variable value that is more often found in the corresponding column. In fact, the method developed is a modification of the well known tabu decision-repair method [Jus02, Cha04] for the problem of processing the compressed tables proposed. The scheme of the method is as follows: 1. A partial order is designated for the domain of each variable on the values of variables (like in the local search algorithm proposed above). 2. Partial assignments are extended iteratively until a) an illegal assignment is found (change to step 3 of the algorithm); b) an legal assignment is found (change to step 4) or c) the number of trials is exhausted (change to step 5). In so doing, use is made of the following heuristics to choose a variable and the values of the variable: a variable with minimum domain is chosen, then, a choice is made of the variable value which is the most of- ten found in the corresponding column. In the course of carrying out assignment, the 𝐷-system is reduced in accordance with the reduction rules proposed earlier. 3. In case an inconsistent partial (or complete) assignment is found, the local search pro- cedure is carried out instead of backtracking. The inconsistent partial assignment based on Consequence 2.1, is formed up to the sub-space in the illegal partial assignments space for the variable set specified. The found conflicts (assignments resulting in empty rows formation in the 𝐷-system) are recorded in special memory formed on a queue principle. It is expedient to limit the queue by a small number of elements. Based on the quantity of conflicts (empty rows of the 𝐷-system), choice is made of the variable participating in the maximum number of conflicts. The partial assignment is modified by calculation of the addition to the partial assignment component, which cor- responds to the conflict variable chosen. Change to step 2. 4. The legal assignment is extended, based on Consequence 2.2, to the domain in the legal assignments space. 5. The end. The method proposed has been successfully utilized in solving a problem of planning of localizing the consequences of on-land oil products spills at one of the subdivisions of the JSC "Apatit", the Kirovsk Branch of FosAgro. Consider the basic scheme of the method proposed (with no additional possibilities for ac- celeration, i.e., taking no account of the relations of domination), with an "𝑁 -Queens" problem taken as an example. 4.4. An example of the hybrid search method application In our case, the chessboard is 4 Γ— 4 in size. The problem is to find one of the possible variants of four queens arrangement on the chessboard so that they are not threatened by each other. The similar formulation of the problem has been considered earlier in [Zue18c], where we proposed to formalize the problem by using the 𝐷-system and made an assessment of the backtracking methods developed by the authors. In the present study the "𝑁 -Queens" problem is solved by a new hybrid method. Let’s match variable 𝑋𝑖 with the 𝑖-th horizontal. In this case the domain of each variable (attribute) is {π‘Ž, 𝑏, 𝑐, 𝑑}. Now let’s set a constraint "two queens arranged on horizontals 1 and 2, are not threatened by each other" in the form of the 𝐷-system: 𝑋1 𝑋2 {π‘Ž, 𝑏, 𝑐, 𝑑} {π‘Ž, 𝑏, 𝑐, 𝑑} 1 ⎀ {𝑏, 𝑐, 𝑑} {𝑐, 𝑑}⎑ βŽ₯ ⎒ 2 βŽ₯ {π‘Ž, 𝑐, 𝑑} {𝑑} ⎒ 3 βŽ₯ {π‘Ž, 𝑏, 𝑑} {π‘Ž} ⎒ βŽ₯ 4 {π‘Ž, 𝑏, 𝑐} {π‘Ž, 𝑏}⎒ ⎦ ⎣ All the names of variables and their current domains are enumerated in the title of the 𝐷- system. The first row of the 𝐷-system, particularly, formalizes that if a queen is on field π‘Ž1 (the place where the first horizontal and the first vertical are intersected), then, on the second horizontal, the other queen may occupy only fields 𝑐2 or 𝑑2 . In the language of logic, it is expressed as follows: (𝑋1 ∈ {π‘Ž}) β†’ (𝑋2 ∈ {𝑐, 𝑑}) or Β¬(𝑋1 ∈ {π‘Ž}) ∨ (𝑋2 ∈ {𝑐, 𝑑}) or (𝑋1 ∈ {𝑏, 𝑐, 𝑑}) ∨ (𝑋2 ∈ {𝑐, 𝑑}). If we compare different pairs of horizontals, we can write down all the constraints on the inter-relative arrangement of all the 4 queens. Thus the CSP described can be expressed in the form of the 𝐷-system: 𝑋1 𝑋2 𝑋3 𝑋4 {π‘Ž, 𝑏, 𝑐, 𝑑} {π‘Ž, 𝑏, 𝑐, 𝑑} {π‘Ž, 𝑏, 𝑐, 𝑑} {π‘Ž, 𝑏, 𝑐, 𝑑} 1 ⎀ {𝑏, 𝑐, 𝑑} {𝑐, 𝑑} βˆ… βˆ… ⎑ 2 βŽ₯ {π‘Ž, 𝑐, 𝑑} {𝑑} βˆ… βˆ… ⎒ βŽ₯ ⎒ 3 βŽ₯ {π‘Ž, 𝑏, 𝑑} {π‘Ž} βˆ… βˆ… ⎒ 4 βŽ₯ {π‘Ž, 𝑏, 𝑐} {π‘Ž, 𝑏} βˆ… βˆ… ⎒ 5 βŽ₯ βˆ… {𝑏, 𝑐, 𝑑} {𝑐, 𝑑} βˆ… ⎒ βŽ₯ ⎒ 6 βŽ₯ βˆ… {π‘Ž, 𝑐, 𝑑} {𝑑} βˆ… ⎒ 7 βŽ₯ βˆ… {π‘Ž, 𝑏, 𝑑} {π‘Ž} βˆ… ⎒ 8 βŽ₯βŽ₯ βˆ… {π‘Ž, 𝑏, 𝑐} {π‘Ž, 𝑏} βˆ… ⎒⎒ 9 βŽ₯ βˆ… βˆ… {𝑏, 𝑐, 𝑑} {𝑐, 𝑑}⎒ 10 βŽ₯ βˆ… βˆ… {π‘Ž, 𝑐, 𝑑} {𝑑} ⎒ βŽ₯ ⎒ 11 βŽ₯ βˆ… βˆ… {π‘Ž, 𝑏, 𝑑} {π‘Ž} ⎒ . 12 βŽ₯ βˆ… βˆ… {π‘Ž, 𝑏, 𝑐} {π‘Ž, 𝑏}⎒ 13 βŽ₯βŽ₯ {𝑏, 𝑐, 𝑑} βˆ… {𝑏, 𝑑} βˆ… ⎒⎒ 14 βŽ₯ {π‘Ž, 𝑐, 𝑑} βˆ… {π‘Ž, 𝑐} βˆ… ⎒ 15 βŽ₯ {π‘Ž, 𝑏, 𝑑} βˆ… {𝑏, 𝑑} βˆ… ⎒ βŽ₯ ⎒ 16 βŽ₯ {π‘Ž, 𝑏, 𝑐} βˆ… {π‘Ž, 𝑐} βˆ… ⎒ 17 βŽ₯ βˆ… {𝑏, 𝑐, 𝑑} βˆ… {𝑏, 𝑑}⎒ 18 βŽ₯ βˆ… {π‘Ž, 𝑐, 𝑑} βˆ… {π‘Ž, 𝑐}⎒ βŽ₯ ⎒ 19 βŽ₯ βˆ… {π‘Ž, 𝑏, 𝑑} βˆ… {𝑏, 𝑑}⎒ 20 βŽ₯ βˆ… {π‘Ž, 𝑏, 𝑐} βˆ… {π‘Ž, 𝑐}⎒ βŽ₯ ⎒ 21 βŽ₯ {𝑏, 𝑐, 𝑑} βˆ… βˆ… {𝑏, 𝑐}⎒ 22 βŽ₯ {π‘Ž, 𝑐, 𝑑} βˆ… βˆ… {π‘Ž, 𝑐, 𝑑}⎒ βŽ₯ 23 {π‘Ž, 𝑏, 𝑑} βˆ… βˆ… {π‘Ž, 𝑏, 𝑑}⎒ βŽ₯ ⎒ 24 ⎦ {π‘Ž, 𝑏, 𝑐} βˆ… βˆ… {𝑏, 𝑐}⎣ Start solving from constructing a partial assignment. Assume that attribute 𝑋1 is chosen and its value π‘Ž is considered. This partial assignment can be expressed as the 𝐢-system 𝐴𝑠𝑠1[𝑋1 ] = [{π‘Ž}]. Now it is necessary to "tune" the initial 𝐷-system to a new domain of attribute 𝑋1 , i.e., a set {π‘Ž}. When tuning, rows 2, 3, 4, 14, 15, 16, 22, 23, 24 are eliminated from the 𝐷-system according to S4’. The rest of the 𝐷-system: 𝑋2 𝑋3 𝑋4 {π‘Ž, 𝑏, 𝑐, 𝑑} {π‘Ž, 𝑏, 𝑐, 𝑑} {π‘Ž, 𝑏, 𝑐, 𝑑} 1 ⎀ {𝑐, 𝑑} βˆ… βˆ… ⎑ βŽ₯ 5 {𝑏, 𝑐, 𝑑} {𝑐, 𝑑} βˆ… ⎒ βŽ₯ ⎒ 6 βŽ₯ {π‘Ž, 𝑐, 𝑑} {𝑑} βˆ… ⎒ 7 βŽ₯ {π‘Ž, 𝑏, 𝑑} {π‘Ž} βˆ… ⎒ βŽ₯ ⎒ 8 βŽ₯ {π‘Ž, 𝑏, 𝑐} {π‘Ž, 𝑏} βˆ… ⎒ 9 βŽ₯ βˆ… {𝑏, 𝑐, 𝑑} {𝑐, 𝑑}⎒ 10 βŽ₯ βˆ… {π‘Ž, 𝑐, 𝑑} {𝑑} ⎒ . βŽ₯ ⎒ 11 βŽ₯ βˆ… {π‘Ž, 𝑏, 𝑑} {π‘Ž} ⎒ 12 βŽ₯ βˆ… {π‘Ž, 𝑏, 𝑐} {π‘Ž, 𝑏}⎒ βŽ₯ 13 βŽ₯ βˆ… {𝑏, 𝑑} βˆ… ⎒⎒ 17 βŽ₯ {𝑏, 𝑐, 𝑑} βˆ… {𝑏, 𝑑}⎒ 18 βŽ₯ {π‘Ž, 𝑐, 𝑑} βˆ… {π‘Ž, 𝑐}⎒ βŽ₯ ⎒ 19 βŽ₯ {π‘Ž, 𝑏, 𝑑} βˆ… {𝑏, 𝑑}⎒ 20 βŽ₯ {π‘Ž, 𝑏, 𝑐} βˆ… {π‘Ž, 𝑐}⎒ βŽ₯ 21 ⎦ βˆ… βˆ… {𝑏, 𝑐}⎒⎣ Rows (tuples) 1, 13, 21 contain one non-empty component each. "Tune" the 𝐷-system to new domains: 𝑋2 βˆ’ {𝑐, 𝑑}, 𝑋3 βˆ’ {𝑏, 𝑑}, 𝑋4 βˆ’ {𝑏, 𝑐}. According to S5’, eliminate "redundant" values from the components. According to S4’, eliminate rows 1, 5, 6, 9, 11, 13, 17, 18, 21 containing full components. We obtain: 𝑋2 𝑋3 𝑋4 {𝑐, 𝑑} {𝑏, 𝑑} {𝑏, 𝑐} 7 ⎀ {𝑑} βˆ… βˆ…βŽ‘ βŽ₯ 8 {𝑐} {𝑏} βˆ…βŽ’ βŽ₯ ⎒ . 10 βŽ₯ βˆ… {𝑑} βˆ…βŽ’ 12 βŽ₯ βˆ… {𝑏} {𝑏}⎒ 19 βŽ₯ {𝑑} βˆ… {𝑏}⎒ βŽ₯ ⎒ 20 ⎦ {𝑐} βˆ… {𝑐}⎣ The analysis of row 7 has shown that the domain of variable 𝑋2 should be reduced to {𝑑}. Then taking into account a new domain of variable 𝑋2 , from the analysis of row 8, it follows that domain 𝑋3 becomes equal to {𝑏}, and the analysis of row 20 allows reduction of the domain of variable 𝑋4 to {𝑐}. That is, we obtain the following complete assignment {(𝑋1 , π‘Ž), (𝑋2 , 𝑑), (𝑋3 , 𝑏), (𝑋4 , 𝑐)}. However, the values of the variables are in conflict with row 10 of the 𝐷-system specifying the problem. It means that a conflict {(𝑋1 , π‘Ž), (𝑋3 , 𝑏)} is found: because row 10 of the initial 𝐷-system contains non-empty components only in positions 𝑋1 and 𝑋3 . Hence, partial assignment 𝐴𝑠𝑠1[𝑋1 ] = [{π‘Ž}], which caused the conflict, gets in a queue of tabu states. The feature of the method is that the propagation process is going on even under the conditions of the conflict found earlier. At this moment the component implementing the local search, starts functioning. Among all the variables included into the partial assignment, the variable participating in the maximum number of conflicts, is chosen. As in the partial assignment 𝐴𝑠𝑠1[𝑋1 ] = [{π‘Ž}] there is only one variable 𝑋1 participating in the only conflict, a new partial assignment is obtained by taking the complement of the component {π‘Ž}: 𝐴𝑠𝑠2[𝑋1 ] = [{𝑏, 𝑐, 𝑑}]. Then "tune" the initial 𝐷-system to a newly formed partial assignment. Having "tuned" the 𝐷-system to a new domain {𝑏, 𝑐, 𝑑}, we have: 𝑋1 𝑋2 𝑋3 𝑋4 {𝑏, 𝑐, 𝑑} {π‘Ž, 𝑏, 𝑐, 𝑑} {π‘Ž, 𝑏, 𝑐, 𝑑} {π‘Ž, 𝑏, 𝑐, 𝑑} 2 ⎀ {𝑐, 𝑑} {𝑑} βˆ… βˆ… ⎑ 3 βŽ₯ {𝑏, 𝑑} {π‘Ž} βˆ… βˆ… ⎒ 4 βŽ₯βŽ₯ {𝑏, 𝑐} {π‘Ž, 𝑏} βˆ… βˆ… ⎒⎒ 5 βŽ₯ βˆ… {𝑏, 𝑑} {𝑐, 𝑑} βˆ… ⎒ 6 βŽ₯ βˆ… {π‘Ž, 𝑑} {𝑑} βˆ… ⎒ βŽ₯ ⎒ 8 βŽ₯ βˆ… {π‘Ž, 𝑏} {π‘Ž, 𝑏} βˆ… ⎒ 9 βŽ₯ βˆ… βˆ… {𝑏, 𝑐, 𝑑} {𝑐, 𝑑}⎒ βŽ₯ 10 βŽ₯ βˆ… βˆ… {π‘Ž, 𝑐, 𝑑} {𝑑} ⎒⎒ 11 βŽ₯ βˆ… βˆ… {π‘Ž, 𝑏, 𝑑} {π‘Ž} ⎒ . 12 βŽ₯ βˆ… βˆ… {π‘Ž, 𝑏, 𝑐} {π‘Ž, 𝑏}⎒ βŽ₯ ⎒ 14 βŽ₯ {𝑐, 𝑑} βˆ… {π‘Ž, 𝑐} βˆ… ⎒ 15 βŽ₯ {𝑏, 𝑑} βˆ… {𝑏, 𝑑} βˆ… ⎒ βŽ₯ 16 βŽ₯ {𝑏, 𝑐} βˆ… {π‘Ž, 𝑐} βˆ… ⎒⎒ 17 βŽ₯ βˆ… {𝑏, 𝑑} βˆ… {𝑏, 𝑑}⎒ 18 βŽ₯ βˆ… {π‘Ž, 𝑑} βˆ… {π‘Ž, 𝑐}⎒ βŽ₯ ⎒ 20 βŽ₯ βˆ… {π‘Ž, 𝑏} βˆ… {π‘Ž, 𝑐}⎒ 22 βŽ₯ {𝑐, 𝑑} βˆ… βˆ… {π‘Ž, 𝑐, 𝑑}⎒ βŽ₯ 23 {𝑏, 𝑑} βˆ… βˆ… {π‘Ž, 𝑏, 𝑑}⎒ βŽ₯ ⎒ 24 ⎦ {𝑏, 𝑐} βˆ… βˆ… {𝑏, 𝑐}⎣ Then it is necessary to extend partial assignments. Choose one of the variables containing a minimum quantity of values in the domain to extend the partial assignment. Let variable 𝑋2 be chosen. In the column which corresponds to variable 𝑋2 , the value a occurs 6 times, and the values 𝑏 and 𝑑 occur 5 times each. Hence, we choose the value π‘Ž. Then consider partial assignment 𝐴𝑠𝑠3[𝑋1 𝑋2 ] = [{𝑏, 𝑐, 𝑑}{π‘Ž}]. As a result of the initial 𝐷- system "tuning", which specifies the conditions of the problem, we obtain specified values of all the variables, not violating any constraints: 𝐴𝑠𝑠4[𝑋1 𝑋2 𝑋3 𝑋4 ] = [{𝑐}{π‘Ž}{𝑑}{𝑏}]. Hence, we have reached the solution of the problem: the first queen is on field 𝑐1 , the second one is on field π‘Ž2 , the third one is on field 𝑑3 , and the fourth one is on field 𝑏4 (Figure 4). 5. Conclusions For the first time, the hybrid methods have been developed to solve non- quantitative constraint satisfaction problems formalized by the 𝐢- and 𝐷-systems. The pecu- liar feature of the methods proposed is that these methods do not use backtracking strategies Figure 4: One of the possible solutions of the "4-Queens" problem resulting often in the exponential increase of computation time, under the increase in the size of the problem. The first hybrid method proposed integrates the author’s methods of non-quantitative con- straint propagation and the existing algorithms of structural constraint graph decomposition. The main computational difficulty connected with application of this method is in the compo- nent implementing the structural constraint graph decomposition, but there are the approx- imated ("greedy") algorithms allowing this decomposition to be rather quickly implemented. Each sub-problem with a tree structure, takes polynomial time to be solved by the author’s non-quantitative constraint propagation algorithms. The method suits well to the situations when there is a series of CSPs with graphs of the similar structure. For instance, the situation like this often occurs in analyzing typical queries to the data storage. The second hybrid method integrates the following components: the author’s methods of non-quantitative constraint propagation to reduce the solution space; the method of local search on partial assignments to quickly quit the sub-spaces containing no solution; the tabu search method to avoid repeated analyzing the states already studied. This method is to be applied to the situations when it is necessary to reach the solution using large bodies of infor- mation, with no a priori information on the CSP graph structure. The method suits well the problems connected with planning and scheduling. Specialized structures applied in representation and processing the table constraints make it possible to reduce memory consumption for the problem representation, and the detailed anal- ysis of the 𝐢- and 𝐷-systems properties underlies the ways of the computational procedures acceleration. Acknowledgments The work was supported by the Russian fund of basic researches (RFFI) – grants 17-29-07021-ofi_m, 18-07-00615-a, 20-07-00708-a. References [Blu11] C. Blum, J. Puchinger, G. Raidl, A. Roli. Hybrid metaheuristics in combinatorial opti- mization: A survey. Applied Soft Computing, 11(6):4135–4151, 2011. [Cha04] K. Chatzikokolakis, G. Boukeas, P. Stamatopoulos. Construction and Repair: A Hybrid Approach to Search in CSPs. Methods and Applications of Artificial Intelligence. SETN 2004. Lecture Notes in Computer Science, 3025:342–351, 2004. [Che10] K. C. Cheng, R. H. Yap. An MDD-based generalized arc consistency algorithm for posi- tive and negative table constraints and some global constraints. Constraints, 15(2):265– 304, 2010. [Dec87] R. Dechter, J. Pearl. Network-based heuristics for constraint satisfaction problems. Artificial Intelligence, 34(1):1–38, 1987. [Dec89] R. Dechter, J. Pearl. Tree clustering for constraint networks. Artificial Intelligence, 38(3):353–366, 1989. [Dec90] R. Dechter. Enhancement schemes for constraint processing: Backjumping, learning and cutset decomposition. Artificial Intelligence, 41(3):273–312, 1990. [Fei18] A. A. Feitosa Neto, A. M. P. Canuto, J. C. Xavier-Junior. Hybrid Metaheuristics to the Automatic Selection of Features and Members of Classifier Ensembles. Information, 9:268, 2018. [Fre82] E. C. Freuder. A sufficient condition for backtrack-free search. Journal of the ACM, 29(1):24–32, 1982. [Fre85] E. C. Freuder. A sufficient condition for backtrack-bounded search. Journal of the ACM, 32(4):755–761, 1985. [Jeg17] P. JΓ©gou, C. Terrioux. Combining restarts, nogoods and bag-connected decompositions for solving CSPs. Constraints, 22:191–229, 2017. [Jus02] N. Jussien, O. Lhomme. Local search with constraint propagation and conflict-based heuristics. Artificial Intelligence, 139:21–45, 2002. [Kat07] G. Katsirelos, T. Walsh. A Compression Algorithm for Large Arity Extensional Con- straints. Principles and Practice of Constraint Programming – CP 2007. Lecture Notes in Computer Science, 4741:379–393, Springer, Berlin, Heidelberg, 2007. [Kul15] B. Kulik, A. Zuenko, A. Fridman. Deductive and defeasible reasoning on the basis of a unified algebraic approach. Scientific and Technical Information Processing, 42(6):402– 410, Allerton Press Inc. 2015. [Lim12] K. Limtanyakul, U. Schwiegelshohn. Improvements of constraint programming and hybrid methods for scheduling of tests on vehicle prototypes. Constraints, 17:172–203, 2012. [Mig01] I. Miguel, Q. Shen. Solution techniques for constraint satisfaction problems: founda- tions. Artificial Intelligence Review, 15:243–267, 2001. [Nat15] M. Nattaf, C. Artigues, P. Lopez. A hybrid exact method for a scheduling problem with a continuous resource and energy constraints. Constraints, 20:304–324, 2015. [Rus10] S. Russel, P. Norvig. Artificial Intelligence: A Modern Approach. 3rd edition. Prentice Hall, 2010. [Ste97] O. Steinmann, A. Strohmaier, T. Stutzle. Tabu search vs. random walk. KI-97: Advances in Artificial Intelligence, 337–348 ,Springer Verlag, Berlin, Germany, 1997. [Tho16] E. Thorstensen. Structural decompositions for problems with global constraints. Con- straints, 21:198–222, 2016. [Ver17] H. Verhaeghe, C. Lecoutre, Y. Deville, P. Schaus. Extending Compact-Table to Basic Smart Tables. Principles and Practice of Constraint Programming. 23rd International Conference, CP 2017, 297–307, Melbourne, VIC, Australia, 2017. [Wan16] R. Wang, W. Xia, R. Yap, Z. Li. Optimizing Simple Tabular Reduction with a bitwise representation. Proceedings of IJCAI 2016, 787–793, 2016. [Zue14] A. A. Zuenko. Vyvod na ogranicheniyakh s primeneniem matrichnogo predstavleniya konechnykh predikatov [Constraint inference based on the matrix representation of finite predicates]. Iskusstvennyi intellekt i prinyatie reshenii [Artificial Intelligence and Decision Making], 3:21–31, 2014. (In russian) [Zue17] A. A. Zuenko, P. A. Lomov, A. G. Oleinik. Application of constraint propagation tech- niques to speed up processing of queries to ontologies. SPIIRAS Proceedings, 1(50):112– 136, 2017. [Zue18a] A. A. Zuenko. Matrix-like Structures for Representation and Processing of Con- straints Over Finite Domains. Proceedings of the Third International Scientific Confer- ence "Intelligent Information Technologies for Industry" (IITI’18, Volume 2), Advances in Intelligent Systems and Computing (AISC), 875:428–438, Springer Nature Switzerland AG, 2019. [Zue18b] A. A. Zuenko. Local Search in Solution of Constraint Satisfaction Problems Repre- sented by Non-Numerical Matrices. Proceedings of the 2nd International Conference on Computer Science and Application Engineering (CSAE ’18), 1–5, ACM New York, NY, USA, 2018. [Zue18c] A. Zuenko, Y. Oleynik. Programming of Algorithms of Matrix-Represented Con- straints Satisfaction by Means of Choco Library. Proceedings of the Third International Scientific Conference "Intelligent Information Technologies for Industry" (IITI’18, Volume 2), Advances in Intelligent Systems and Computing (AISC), 875:439–448, Springer Na- ture Switzerland AG, 2019.