=Paper=
{{Paper
|id=Vol-2648/paper2
|storemode=property
|title=Hybrid Search Methods Based on Table Representation of Non-quantitative Constraints Satisfaction Problems
|pdfUrl=https://ceur-ws.org/Vol-2648/paper2.pdf
|volume=Vol-2648
|authors=Alexander Zuenko
}}
==Hybrid Search Methods Based on Table Representation of Non-quantitative Constraints Satisfaction Problems==
https://ceur-ws.org/Vol-2648/paper2.pdf
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.