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 efective 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.
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 suficiently efective 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 technologies is table constraints. A table form is very suitable for diferent 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 efective methods
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 satisfaction algorithms presented by compressed tables [Che10]. The present paper is a study extending 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 efective, the straint satisfaction problems have been found by the author. 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
An efective search in large-size compressed tables was first organized by specially developed 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 categories: 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.
For it to be solved by the constraint programming technology, any applied problem should be represented as a constraint satisfaction problem. taking part in the constraint, which can be taken by the variables from .
According to [Rus10], the Constraint Satisfaction Problem (CSP) consists of three components: < , , > .
– 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 } for variable . Each constraint is a couple <, > the allowed combinations of variable values. Each domain , where defines a set of a values { 1, ...,
– is a set of variables – is a relation specifying the allowed combinations of values
The assignment which does not violate any constraint, is called a legal assignment. A complete 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 combinations 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 specifying). 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 (geographic 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 [ ] = ⎢ { } ⎢ ⎣ { } {2, 4} {1, 5} ⎡ { } {1, 2, 4, 5} ⎤ [ ] = ⎥ {, } ⎤ {, } ⎥ ⎦ {2, 4} {1, 5} ∅
{1, 2, 4, 5} ⎣ the relations over quantitative (continuous) domains. compared to a full enumerating of their tuples.
Very often, -ary relations specified extensionally, can be represented more compactly if over sets that corresponds to a given -system:
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: – { , below are a
-system, which compactly describes the relation, and an algebraic expression -system [ the same initial relation:
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 relations, is the -system. This matrix is represented in reversed direct brackets. Given below is the ], which is equivalent to the -system [ ] because both systems describe ⎥ = { } × {1, 2, 4, 5} ∪ { } × {2, 4} ∪ { } × {1, 5}. ⎢ = ({, } × {1, 2, 3, 4, 5} ∪ {, , ,
} × {2, 4}) ∩ ⎥ ⎦ ⎡ ⎢ ∩({, } × {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. intersection of subspaces correlated to each of its rows.
Each row of the -system is a union of definite Cartesian products. The -system specifies the designation for the entire range of possible values (domain) of an attribute.
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
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
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 below. second -system. pressed tables.
Now, change to the description of the hybrid search methods for the proposed types of com
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 satisfaction 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 constraint satisfaction problem with a tree structure and by the author’s methods of nonquantitative 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 memory 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 dificult 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.
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 diferent 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 components 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 efective 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 efectively applied in solutions of CSPs that contain 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.
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. the -system are given below. is empty), the row is eliminated. in the corresponding column, these values are eliminated from the given domain.
Statement 3 (S3). If the domain of an attribute of the -system contains values not occurred Statement 4 (S4). If the row of the -system contains at least one empty component (the row 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 componentwise) 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
in the example): Let the following correspondences "attribute – attribute domain" be specified: −{ 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 following set of constraints written in a form of the -systems (their semantics is not essential }. Also specified is the ⎢ { 2} { 3, 4, 5} ⎥
⎢ { 2, 3, 6} { 2} ⎥ 1[ ] { 1, 2} ⎢⎢ { 3} ⎢ { 4} ⎢⎢ { 5} ⎣ { 6} ⎡ { 1} ⎢ { 3} ⎢ { 6} ⎢⎢ { 2} { 2, 3} ⎥⎥ ⎢⎣ { 7} { 5, 6} ⎦
⎥
{ 1, 6} ⎢ { 2, 3, 4} { 4, 6} { 5, 7} ⎢⎢ { 8, 9, 11} ⎢ { 9, 11, 14} ⎢ { 10, 13}
The task is to calculate the join of the present relations, i.e., it is necessary to find: 1[ ] ⋊⋉ CSP is partitioned into sub-problems by 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[ ]
. becomes a singleton set { 1}.
It is possible, in advance, to calculate the corresponding multi-place relation for each subproblem 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 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 nonquantitative 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 problem: 3[ }]. So, we have finished moving from constraint 2[ ] to constraint 1[ constraint 1[
] is activated and, being "tuned" to a new domain of variable , takes the form 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] and taking into account a new domain of variable , we reduced to { 1, 6}. Finally, constraint 5[ specified domains, is converted to vector-row [{ 1} { 1}]. 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[ vector-row [{ 1} { 1}], and the domain of variable is reduced to { 1 ], is converted into }. After that constraint 6[ ] is analyzed, being reduced to vector-row [{
1, 6} { 1}]. The domain of variable is ] is activated, which, taking into account all the 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 ifve assignments left are made in the same way. The results of all the steps can be classified into two -systems.
⎢ ⎢ 1 ⎡ 2 ⎢ 3 ⎢ 4 ⎢
⎢ 5 ⎢ 6 ⎢ 7 ⎢ 8 ⎢ 9 ⎢ ⎣
{ 1} { 1} { 2} { 3} { 2} { 2} { 4} { 5} { 6} for polynomial time according to Theorem 1.
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
Next, we consider the second of the developed hybrid methods.
Constraint propagation methods and local search methods are known to possess low computational 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.
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 eliminated 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 nonempty 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 eliminated (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 domains 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 statements above, the well known arc and node consistency algorithms were modified for cases of non-quantitative constraints [Zue18a].
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 difer in methods of ifnding 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 solution 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 interpreted 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 assignment which difers 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. contain the values and , respectively.
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 introduced as follows: scheme ) with the domain ≤ , if and only if { } ⊆ { }, where: , ∈
; and { } and { } , then, for the values from , the partial order relation "≤" is are the sets of the numbers of the rows of the -system whose components of the attribute
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 the number of conflicts generated by the second assignment is not greater than that generated
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
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 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 attribute. 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: − { }, − {, , ℎ, }, − {, , }.
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 often 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 procedure 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 corresponds 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 acceleration, i.e., taking no account of the relations of domination), with an " -Queens" problem taken as an example.
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 diferent 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 {, , , 1 ⎤ {, , 2 ⎥ {, , 3 ⎥⎥ {, , 4 ⎥ {, , 5 ⎥⎥ ∅ 6 ⎥ ∅ 7 ⎥ ∅ 8 ⎥⎥ ∅ 9 ⎥ ∅ 1110 ⎥⎥⎥ ∅∅ 12 ⎥ ∅ 13 ⎥⎥ {, , 14 ⎥ {, , 15 ⎥ {, ,
⎥ 16 ⎥ {, , 17 ⎥ ∅ 18 ⎥⎥ ∅ 19 ⎥ ∅ 20 ⎥ ∅
⎥ 21 ⎥ {, , 22 ⎥ {, , 23 ⎥ {, ,
⎥ 24 ⎦ {, , } } } } } } } } } } } } }
} 2 {, , , {, } { } { } {, } {, , {, , {, , {, , ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ {, , {, , {, , {, , ∅ ∅ ∅ ∅ } } } } } } } }
3 {, , , ∅ ∅ ∅ ∅ {, } { } { } {, } {, , {, , {, , {, , {, } {, } {, } {, } ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ } } } } }
4 {, , ,
} ∅ ⎡ ∅ ⎢
⎢ ∅ ⎢ ∅ ⎢ ∅ ⎢
⎢ ∅ ⎢ ∅ ⎢ ∅ ⎢⎢ {, }⎢ { } ⎢
⎢ { } ⎢ . {, }⎢ ∅ ⎢⎢ ∅ ⎢ ∅ ⎢
⎢ ∅ ⎢ {, }⎢ {, }⎢⎢ {, }⎢ {, }⎢ {, }⎢⎢ {, , ⎢} {, , ⎢⎢} {, }⎣
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: 4 } {, , ,
} 3 } {, , ,
∅ {, } { } { } {, } {, , {, , {, , {, , {, } ∅ ∅ ∅ ∅ ∅ 2 {, , , 1 ⎤ {, } 5 ⎥⎥ {, , 6 ⎥ {, , 7 ⎥ {, , 8 ⎥⎥ {, , 9 ⎥ ∅ 10 ⎥⎥ ∅ 11 ⎥ ∅ 12 ⎥ ∅ 13 ⎥⎥ ∅ 17 ⎥ {, , 18 ⎥ {, ,
⎥ 19 ⎥ {, , 20 ⎥ {, , 21 ⎦⎥ ∅ 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:
For the first time, the hybrid methods have been developed to solve nonquantitative constraint satisfaction problems formalized by the - and -systems. The peculiar feature of the methods proposed is that these methods do not use backtracking strategies 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 constraint propagation and the existing algorithms of structural constraint graph decomposition. The main computational dificulty connected with application of this method is in the component implementing the structural constraint graph decomposition, but there are the approximated ("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 information, 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 analysis 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. [Tho16] E. Thorstensen. Structural decompositions for problems with global constraints. Constraints, 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 ifnite 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 techniques 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 Constraints Over Finite Domains. Proceedings of the Third International Scientific Conference "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 Represented 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 Constraints 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 Nature Switzerland AG, 2019.