# A Divide-and-Conquer Approach for Solving Fuzzy Max-Archimedeant-Norm Relational Equations

Authors: Jun-Lin Lin; Hung-Chjh Chuan; Laksamee Khomnotai
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

A system of fuzzy relational equations with the max-Archimedeant-norm composition was considered. The relevant literature indicated that this problem can be reduced to the problem of finding all the irredundant coverings of a binary matrix. A divide-and-conquer approach is proposed to solve this problem and, subsequently, to solve the original problem. This approach was used to analyze the binary matrix and then decompose the matrix into several submatrices such that the irredundant coverings of the original matrix could be constructed using the irredundant coverings of each of these submatrices. This step was performed recursively for each of these submatrices to obtain the irredundant coverings. Finally, once all the irredundant coverings of the original matrix were found, they were easily converted into the minimal solutions of the fuzzy relational equations. Experiments on binary matrices, with the number of irredundant coverings ranging from 24 to 9680, were also performed. The results indicated that, for test matrices that could initially be partitioned into more than one submatrix, this approach reduced the execution time by more than three orders of magnitude. For the other test matrices, this approach was still useful because certain submatrices could be partitioned into more than one submatrix.


---

## Body

## 1. Introduction

Solving a system of fuzzy relational equations is a subject of great scientific interest [1, 2]. This work considers a system of fuzzy relational equations of the form
(1)
max
⁡
{
t
(
x
1
,
a
11
)
,
t
(
x
2
,
a
21
)
,
…
,
t
(
x
m
,
a
m
1
)
}
=
b
1
max
⁡
{
t
(
x
1
,
a
12
)
,
t
(
x
2
,
a
22
)
,
…
,
t
(
x
m
,
a
m
2
)
}
=
b
2
…
,
max
⁡
{
t
(
x
1
,
a
1
n
)
,
t
(
x
2
,
a
2
n
)
,
…
,
t
(
x
m
,
a
m
n
)
}
=
b
n
,
where a
i
j, b
j, x
i
∈
[
0,1
] for each i, 1
⩽
i
⩽
m and for each j, 1
⩽
j
⩽
n and t represents a continuous Archimedean t-norm function. System (1) can be succinctly written in the following equivalent matrix form:
(2)
X
∘
A
=
B
,
where X
=
(
x
i
)
1
×
m is the matrix of unknowns, A
=
(
a
i
j
)
m
×
n is the matrix of coefficients, B
=
(
b
j
)
1
×
n is the right-hand side of the system, and the symb “∘” represents a max-Archimedean t-norm composition.Di Nola et al. [3] indicated that, given a continuous t-norm for t in system (1) and assuming the existence of solutions, the solution set of system (1) can be fully determined by the greatest solution and a finite number of minimal solutions. It is well-known that the greatest solution can be easily computed, but finding all minimal solutions is difficult. Li and Fang [4] demonstrated that the systems of max-t-norm equations can be divided into two categories, depending on the function t in the system. When t is continuous and Archimedean, the minimal solutions correspond one-to-one to the irredundant coverings of a set covering problem. When t is continuous and non-Archimedean, the minimal solutions correspond to a subset of constrained irredundant coverings of a set covering problem. Li and Fang [5] discussed the necessary and sufficient conditions for solving max-t-norm equations. A survey of similar and other related works is described in [5].This work focuses on system (1), with t representing a continuous Archimedean t-norm function. Although solving such a system is equivalent to solving a set covering problem, set covering problems are classified as NP-hard problems [5, 6]. Therefore, solving a system of max-Archimedean t-norm equations is NP-hard. Wu and Guu [7] demonstrated that the number of minimal solutions of such a system can grow exponentially as the numbers of variables and equations (i.e., m and n in system (1)) increase. Therefore, solving system (1) that has hundreds or thousands of minimal solutions is not uncommon and can be a challenge.The concept of partitioning involves grouping related variables and equations and separating unrelated variables and equations. A variablex
i and the jth equation (i.e., max
⁡
{
t
(
x
1
,
a
1
j
)
,
…
,
t
(
x
m
,
a
m
j
)
=
b
j
}) in system (1) arerelated if the value of x
i can affect whether the jth equation holds. Furthermore, two variables (or two equations or one variable and one equation) in system (1) are related if they are related to a common variable or equation. In system (1) with numerous variables and equations (i.e., m and n are high), it is likely that not all variables and equations are related to one another. Consequently, system (1) may be partitioned into several subsystems, each containing only the related variables and equations. Thus, the original problem is decomposed into several subproblems. Because solving system (1) is an NP-hard problem [5, 6], solving several smaller subproblems is considerably faster than solving the original problem directly. Therefore, partitioning can expedite the process of solving system (1). Notably, even if all variables and equations of system (1) are related, partitioning can still be applied to the subsets of all the variables and equations. For example, many approaches involve reducing system (1) by fixing the value of a certain variable x
i (Rule 5 in Section 5 provides an example). Subsequently, the remaining variables and equations can be partitioned into more than one group such that each group contains only the related variables and equations. The concept of partitioning is discussed further in Section 4.Based on the concept of partitioning, the first objective of this study was to develop a divide-and-conquer approach for finding all of the minimal solutions of system (1). In this approach, system (1) is first transformed into a binary binding matrix. We propose an algorithm, called PA, in which the concept of partitioning is applied to decompose the binary binding matrix into several submatrices, the irredundant coverings of each submatrix are constructed recursively, and, finally, they are used to form the irredundant coverings of the binary binding matrix. Once all of the irredundant coverings of the binary binding matrix are found, they can be easily converted into the minimal solutions of system (1).Numerous studies on solving system (1) have been conducted [7–9], but few have provided a performance study of the methods used for solving system (1) in which hundreds or thousands of minimal solutions are involved. Wu and Guu [7] used their method to solve test problems for which the number of minimal solutions ranged from 6 to 100, and the results indicated (Figure 1) that all test problems can be solved in less than 300 ms by using an ordinary PC. However, test problems solved by using such a scale do not fully reflect the difficulty of solving system (1). One problem that hinders the process of performing tests on a large scale is that generating test cases in which system (1) has a high number of minimal solutions is complex.Figure 1
Number of minimal solutions versus execution time (in ms) reported in [7].To bypass the need to generate complex system (1) test cases, large binary matrices can be generated because any system (1) case can be reduced to a binary matrix, called abinary binding matrix, and the problem of solving system (1) can be reduced to the problem of finding all of the irredundant coverings of the binary binding matrix. According to Lin [8], both the reduction process and the conversion of an irredundant covering to a minimal solution can be conducted in polynomial time and, therefore, finding all irredundant coverings is the core process executed in solving system (1). In other words, the time required to find all of the irredundant coverings of the binary binding matrix accounts for most of the time required to solve system (1). This is especially true for complex system (1) cases because the time used for both the reduction of system (1) and the conversion of irredundant coverings to minimal solutions is insubstantial compared with the time used for finding all irredundant coverings. Therefore, the time required to find all irredundant coverings when adopting the proposed approach can be used to represent the performance of this approach. The second objective of this study was to develop an algorithm for generating binary matrices with various characteristics on a considerably large scale to enable the evaluation of the performance of various approaches in finding all irredundant coverings on the test matrices that are difficult to solve.To evaluate the impact of partitioning on the execution time, the proposed algorithm (PA) was compared with another approach (denoted as the non-PA) proposed by Markovskii [6] for finding all irredundant coverings. The only difference between the PA and non-PA is that the PA contains an additional step for incorporating the concept of partitioning. Several test matrices were generated for this performance study. For test matrices that can be initially partitioned into more than one submatrix, the PA reduces the execution time required by the non-PA by more than three orders of magnitude. Even for test matrices that cannot be initially partitioned into more than one submatrix, the PA still offers more favorable performance than does the non-PA. This is attributed to the partitioning of the submatrices of the binary binding matrix.The rest of this paper is organized as follows. In Section2, the preliminaries of Archimedean t-norm are given. In Section 3, the procedure for constructing the binary binding matrix and minimal solutions is presented. In Section 4, the concept of partitioning is discussed and an algorithm for finding all irredundant coverings is proposed in Section 5. In Section 6, the procedure for generating test matrices is described and the performance results are presented. Finally, conclusion is given in Section 7.


## 2. Preliminaries

This section describes the basic concepts oft-norm, Archimedean t-norm, and the greatest solution and minimal solutions of fuzzy relational equations. Please refer also to [3–5, 9, 10].A triangular norm (t-norm for short) is a binary function mapping from [
0,1
]
2 to [
0,1
] that satisfies the following conditions:(1)
t
(
a
,
b
)
=
t
(
b
,
a
) (commutativity),
(2)
t
(
a
,
t
(
b
,
c
)
)
=
t
(
t
(
a
,
b
)
,
c
) (associativity),
(3)
t
(
a
,
b
)
⩽
t
(
a
,
c
), if b
⩽
c (monotonicity),
(4)
t
(
a
,
0
)
=
0 and t
(
a
,
1
)
=
a, for any a
=
[
0,1
] (boundary condition).A well-known fact is thatt
(
a
,
b
)
⩽
min
⁡
{
a
,
b
} for any t-norm. The commonly seen “min” and “product” are both a t-norm function.LetX
(
A
,
B
)
=
{
X
∈
[
0,1
]
m
∣
X
∘
A
=
B
} denote the set of all solution vectors of (2), ℐ
=
{
1,2
,
…
,
m
}, let 𝒥
=
{
1,2
,
…
,
n
} be two index sets, and let X
1
=
(
x
i
1
)
1
×
m and X
2
=
(
x
i
2
)
1
×
m, for all i
∈
ℐ, be two vectors. For any X
1, X
2
∈
X
(
A
,
B
), the relation X
1
⩽
X
2 holds if and only if x
i
1
⩽
x
i
2 for all i
∈
ℐ. A solution X
¯
∈
X
(
A
,
B
) is called the greatest solution if X
⩽
X
¯ for all X
∈
X
(
A
,
B
). Conversely, a solution X
_
∈
X
(
A
,
B
) is a minimal solution if ∀
X
∈
X
(
A
,
B
), where X
⩽
X
_ implies that X
=
X
_. As described in Section 1, with a continuous t-norm for t in system (1), the solution set X
(
A
,
B
) can be completely determined by the greatest solution and a finite number of minimal solutions. This study assumes that t-norms are continuous.The greatest solution of system (1) with a t-norm for t can be computed explicitly using the “→
t” operator defined as
(3)
a
⟶
t
b
=
sup
⁡
{
x
∈
[
0,1
]
∣
t
(
x
,
a
)
⩽
b
}
,
where t
(
x
,
a
) is a t-norm and b
∈
[
0,1
]. If the solution set of system (1) is not empty, then the greatest solution X
¯
=
(
x
¯
i
)
i
∈
ℐ can be calculated as follows:
(4)
x
¯
i
=
min
⁡
j
∈
𝒥
⁡
(
a
i
j
⟶
t
b
j
)
for
each
i
∈
ℐ
.Mostert and Shields [11] subdivided continuous t-norms into three categories, namely, the “min” operation, Archimedean t-norms, and ordinal sums of a family of properly defined Archimedean t-norms. The Archimedean t-norm t is a t-norm with t
(
a
,
a
)
<
a for all 0
<
a
<
1 [3]. Notably, the well-known “min” operation is not an Archimedean t-norm. Wu and Guu [7] collected six Archimedean t-norm functions as follows:(1)
Algebraic product:t
(
a
,
b
)
=
a
b;
(2)
Łukasiewicz t-norm: t
(
a
,
b
)
=
max
⁡
{
0
,
a
+
b
-
1
};
(3)
Einstein product:t
(
a
,
b
)
=
a
b
/
(
1
+
(
1
-
a
)
(
1
-
b
)
);
(4)
Hamacher product:t
(
a
,
b
)
=
a
b
/
(
λ
+
(
1
-
λ
)
(
a
+
b
-
a
b
)
), where 0
⩽
λ
⩽
∞;
(5)
Yu operation:t
(
a
,
b
)
=
max
⁡
{
0
,
(
1
+
λ
)
(
a
+
b
-
1
)
-
λ
a
b
}, where -
1
⩽
λ
⩽
∞;
(6)
Weber operation:t
(
a
,
b
)
=
max
⁡
{
0
,
(
a
+
b
+
λ
a
b
-
1
)
/
(
1
+
λ
)
}, where -
1
⩽
λ
⩽
∞.Simple formula for calculating the greatest solution of system (1) that uses any of these six Archimedean t-norm functions for t is also available in Wu and Guu [7].


## 3. Reduction of Fuzzy Relational Equations to Covering Problem

This section describes the procedure to reduce the problem of finding all minimal solutions of system (1) to the problem of finding all irredundant coverings of the binary binding matrix of system (1). The description follows the results of Lin [8]. Subsequently, in Section 4, we apply the concept of partitioning to the binary binding matrix to expedite finding all irredundant coverings.LetM
=
(
m
i
j
)
|
I
|
×
|
J
| denote a matrix with i
∈
I, j
∈
J and m
i
j
∈
{
0,1
,
2
}, where I and J denote the index sets for the rows and the columns of M, respectively. Notably, both I and J are a set of positive integers. Let I
j
(
M
)
=
{
i
∈
I
∣
m
i
j
≠
0
} denote an index set for each j
∈
J and let J
i
(
M
)
=
{
j
∈
J
∣
m
i
j
≠
0
} denote an index set for each i
∈
I. A set C
⊆
I is acovering of M if ⋃
i
∈
C
‍
J
i
(
M
)
=
J. A covering C isirredundant if each proper subset of C is not a covering of M. The term Φ
(
M
) denotes the set of all irredundant coverings of M.Example 1.
Consider the matrixM below, where the index sets I and J are indicated on the left and on the top of the matrix, respectively. The set of all irredundant coverings of M is Φ
(
M
)
=
{
{
1,2
}
,
{
1,3
}
,
{
2,3
}
}
:
(5)
M
=
1
2
3
4
1
2
3
4
(
1
1
0
2
0
1
1
2
1
0
1
2
0
0
0
2
)
.Thebinding matrix of system (1) is denoted by ℳ
=
(
m
i
j
)
m
×
n and is given by
(6)
m
i
j
=
{
1
if
t
(
x
¯
i
,
a
i
j
)
=
b
j
≠
0
,
2
if
b
j
=
0
,
0
if
t
(
x
¯
i
,
a
i
j
)
≠
b
j
,
for i
∈
ℐ and j
∈
𝒥.According to Expression (6), if b
j
=
0, then m
i
j
=
2 for each i
∈
ℐ; that is, all elements in the jth column of ℳ are 2. Such columns are referred to asall-2-columns in a binding matrix. Let ℳ
* denote a binding matrix ℳ with all of its all-2-columns removed. It is obvious that if B is not a zero vector, then ℳ
* is a binary matrix containing one or more columns and the set of irredundant coverings of ℳ equals that of ℳ
*. The matrix ℳ
* is referred to as thebinary binding matrix of system (1).Example 2.
Consider the following fuzzy relational equations with max-Łukasiewicz t-norm composition:
(7)
X
∘
A
=
B
,
where
A
=
(
0.8
0.9
0.2
0.3
0.1
0.7
0.8
0.1
0.7
0.2
0.9
0
0.9
0.8
0.7
0.9
)
,
f
f
f
f
f
f
f
f
F
f
f
f
f
i
f
f
f
f
f
f
B
=
(
0.5,0.6,0.7,0
)
.The binding matrixℳ is the same as the matrix M in Example 1, while the binary binding matrix ℳ
* is formed by the first three columns of ℳ.Themapping vector of an irredundant covering C
∈
Φ
(
ℳ
*
) is denoted by X
C
=
(
x
i
C
)
i
∈
ℐ and is given by
(8)
x
i
C
=
{
0
if
i
∉
C
,
x
¯
i
otherwise
.LetX
_
(
A
,
B
) denote the set of all minimal solutions of system (1). Lin [8] proved that if B is not a zero vector, then X
_
(
A
,
B
) equals the set of mapping vectors of all irredundant coverings of ℳ
*; that is, X
_
(
A
,
B
)
=
{
X
C
∣
C
∈
Φ
(
ℳ
*
)
}. If B is a zero vector, namely, b
j
=
0 for every j
∈
𝒥, then it is obvious that X
_
(
A
,
B
)
=
{
0
→
}. Therefore, X
_
(
A
,
B
) can be determined with the following procedure.(1)
IfB is a zero vector, then X
_
(
A
,
B
)
=
{
0
→
} and stop.
(2)
Calculate the greatest solutionX
¯ using Expression (4).
(3)
IfX
¯
∉
X
(
A
,
B
), then X
_
(
A
,
B
)
=
∅ and stop.
(4)
Calculate the binding matrixℳ using Expression (6).
(5)
Letℳ
* be obtained from ℳ with all of its all-2-columns removed.
(6)
ConstructΦ
(
ℳ
*
) by searching all irredundant coverings of ℳ
*.
(7)
X
_
(
A
,
B
)
=
{
X
C
∣
C
∈
Φ
(
ℳ
*
)
}, where each X
C is calculated using Expression (8).Example 3.
Consider the fuzzy relational equations in Example2. Since B is not a zero vector, Step (1) is skipped. Step (2) obtains the greatest solution X
¯
=
(
0.7,0.9,0.8,0.1
), and Step (3) then finds that X
¯
∘
A
=
B holds (i.e., X
¯
∈
X
(
A
,
B
)). Step (4) obtains the binding matrix ℳ, which is the same as the matrix M in Example 1. Step (5) obtains the binary binding matrix ℳ
*, which is the same as ℳ but without its fourth column. Step (6) yields Φ
(
ℳ
*
)
=
{
{
1,2
}
,
{
1,3
}
,
{
2,3
}
}. Finally, Step (7) yields X
_
(
A
,
B
)
=
{
(
0.7,0.9,0
,
0
)
,
(
0.7,0
,
0.8,0
)
,
(
0,0.9,0.8,0
)
}.It is obvious that Steps (1)–(5) can be done inO
(
m
n
) time. Li and Fang [4] and Lin [8] proved the bijective (i.e., both one-to-one and onto) mapping between a minimal solution and an irredundant covering, and thus Step (7) can be done in O
(
m
|
X
_
(
A
,
B
)
|
) time, where |
X
_
(
A
,
B
)
| is the number of minimal solutions of (2). Step (6), finding all irredundant coverings, is the most time-consuming step. Therefore, the task of finding all minimal solutions of (2) is reduced to the task of finding all irredundant coverings of a binary matrix, which is the focus of the next two sections.


## 4. Partitioning

This section describes the concept of partitioning a binary matrix into one or more submatrices such that the irredundant coverings of the binary matrix can be derived from the irredundant coverings of these submatrices. First, the notation used is defined as follows to facilitate the discussion.LetM
=
(
m
i
j
)
|
I
|
×
|
J
| denote a binary matrix with i
∈
I and j
∈
J, where I and J denote the index sets for the rows and the columns of M, respectively. Here, both I and J are a set of integers (not necessarily contiguous or starting from 1). Let M
[
I
k
;
J
k
]
=
(
m
i
j
)
|
I
k
|
×
|
J
k
| denote a submatrix of M, where i
∈
I
k
⊆
I and j
∈
J
k
⊆
J; that is, I
k and J
k are the index sets for the rows and the columns of M
[
I
k
;
J
k
], respectively.Example 4.
Consider the matricesM, M
1, and M
2 below, where the index sets for the rows and the columns are, respectively, indicated on the left and on the top of each matrix. The index sets for the rows of M, M
1, and M
2 are I
=
{
1,2
,
3,4
}, I
1
=
{
2,3
}, and I
2
=
{
2,3
}, respectively. The index sets for the columns of M, M
1, and M
2 are J
=
{
1,2
,
3
}, J
1
=
{
3
}, and J
2
=
{
1,2
,
3
}, respectively. Here, M
1
=
M
[
I
1
;
J
1
] is a submatrix of M formed by rows 2 and 3 and column 3. Similarly, M
2
=
M
[
I
2
;
J
2
] is a submatrix of M formed by rows 2 and 3 and columns 1, 2, and 3. Notably, M
1 also equals M
2
[
I
1
;
J
1
] and thus is a submatrix of M
2
:
(9)
M
=
1
2
3
1
2
3
4
(
1
1
0
0
1
1
1
0
1
0
0
0
)
M
1
=
3
2
3
(
1
1
)
M
2
=
1
2
3
2
3
(
0
1
1
1
0
1
)
.Definition 5.
LetM
1 and M
2 be two binary matrices. The ⋈ operator is defined by Φ
(
M
1
)
⋈
Φ
(
M
2
)
=
{
C
1
⋃
C
2
∣
C
1
∈
Φ
(
M
1
)
∧
C
2
∈
Φ
(
M
2
)
}.Given a binary matrixM, then both {
∅
}
⋈
Φ
(
M
)
=
Φ
(
M
) and ∅
⋈
Φ
(
M
)
=
∅ hold.In Section1, we described the concept of partitioning, which involves grouping the related variables and equations of system (1) to reduce the problem size. Because the variables and equations of system (1), respectively, correspond to the rows and columns of its binding matrix, we applied the same concept to the binary binding matrix by grouping the rows and columns that are related. Given a binary matrix M
=
(
m
i
j
), row i and column j arerelated if m
i
j
≠
0. Furthermore, two rows (or two columns or one row and one column) are related if they are related to a common row or column.The matrixM can be considered a bipartite graph G
=
(
I
,
J
,
M
), where the index sets I and J represent the two sets of vertices of G and the matrix M represents the edges that connect the vertices in I and J. If m
i
j
≠
0, then an edge connects the vertex i
∈
I and the vertex j
∈
J. Notably, no edge connects two vertices both in I or both in J. Therefore, if two rows (or two columns or one row and one column) are related, then a path connects the corresponding vertices in G. Because a graph isconnected if every pair of vertices is connected by a path, a connected subgraph of G represents a set of related rows and columns in M. Partitioning is used to find allcomponents (i.e., themaximal connected subgraph) of G. A connected subgraph of G is maximal if vertices and edges that could be added to the subgraph and still leave it connected do not exist in G. Finding all of the components in a bipartite graph is faster than finding all of the components in a general graph because the former can stop as soon as one of the two sets of vertices is fully explored. A formal definition of partitioning is given as follows.Definition 6.
Given a binary matrixM
=
(
m
i
j
)
|
I
|
×
|
J
|, thepartitioning of M, denoted as Ψ
(
M
), is formed by a set of submatrices M
k
=
M
[
I
k
,
J
k
] of M, where k
∈
P
=
{
1,2
,
…
,
|
Ψ
(
M
)
|
} and |
Ψ
(
M
)
| is the number of matrices in Ψ
(
M
), such that the following conditions are satisfied:(1)
⋃
k
∈
P
‍
I
k
=
I and ⋃
k
∈
P
‍
J
k
=
J,
(2)
I
k
′
∩
I
k
*
=
J
k
′
∩
J
k
*
=
∅ for any k
′
,
k
*
∈
P but k
′
≠
k
*,
(3)
m
i
j
=
0 for any i
∈
I
k
′ and j
∈
J
k
*, where k
′
,
k
*
∈
P but k
′
≠
k
*.Example 7.
Consider the binary matrixM below. For ease of exposition, the index sets for the rows and the columns of M are, respectively, indicated on the left and on the top of the matrix:
(10)
M
=
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
(
1
0
1
0
0
0
0
0
0
1
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
0
1
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
1
0
0
1
0
0
0
)
.By Definition6, we have Ψ
(
M
)
=
{
M
1
,
M
2
}, where M
1
=
M
[
{
4,6
,
8
}
,
{
5,8
,
9
}
] and M
2
=
M
[
{
1,2
,
3,5
,
7,9
}, {
1,2
,
3,4
,
6,7
,
10
}
] are shown as
(11)
M
1
=
5
8
9
4
6
8
(
1
1
0
1
0
1
0
1
1
)
,
(12)
M
2
=
1
2
3
4
6
7
10
1
2
3
5
7
9
(
1
0
1
0
0
0
1
0
1
1
0
0
0
1
0
0
0
0
1
1
0
0
0
0
1
1
0
0
1
1
1
0
0
0
0
0
0
0
1
0
1
0
)
.Theorem8 states that if a binary matrix can be partitioned into several submatrices, as described in Definition 6, then the set of irredundant coverings of the binary matrix can be constructed by performing the ⋈ operation on the sets of irredundant coverings of these submatrices.Theorem 8.
Given a binary matrixM, if Ψ
(
M
)
=
{
M
1
,
M
2
,
…
,
M
p
}, then Φ
(
M
)
=
Φ
(
M
1
)
⋈
Φ
(
M
2
)
⋈
⋯
⋈
Φ
(
M
p
).Proof.
LetP
=
{
1,2
,
…
,
p
} and M
k
=
[
I
k
;
J
k
] for each k
∈
P. By Definition 6, Φ
(
M
1
)
⋈
Φ
(
M
2
)
⋈
⋯
⋈
Φ
(
M
p
)
⫅
Φ
(
M
) holds. Assume to the contrary that there exists C
∈
Φ
(
M
) but C
∉
Φ
(
M
1
)
⋈
Φ
(
M
2
)
⋈
⋯
⋈
Φ
(
M
p
). The set C can be decomposed into p disjoint subsets of C such that C
=
⋃
k
∈
P
‍
C
k, where each C
k
⫅
I
k. Since C
∈
Φ
(
M
), by Condition (
3
) of Definition 6, each C
k must be a covering of M
k. If C
k
′
∉
Φ
(
M
k
′
) for some k
′
∈
P, then there exists a covering C
_
k
′
⊂
C
k
′ of M
k
′. Then, (
C
∖
C
k
′
∪
C
_
k
′
)
⊂
C is a covering of M, and consequently C
∉
Φ
(
M
), which contradicts C
∈
Φ
(
M
). Therefore, Φ
(
M
)
⫅
Φ
(
M
1
)
⋈
Φ
(
M
2
)
⋈
⋯
⋈
Φ
(
M
p
).The advantage of using partitioning is twofold. First, partitioning involves decomposing a matrix into several submatrices with a reduced number of rows and columns, the irredundant coverings of which can be found more efficiently than those of the original matrix. Second, if the covering of submatrices is not minimal, then it is immediately discarded and is not combined with the coverings of other submatrices to form new coverings. This substantially reduces the number of redundant coverings generated. Furthermore, once the set of irredundant coverings of each submatrix is found, Theorem8 can be applied to obtain the set of irredundant coverings of the original matrix without generating any redundant coverings of the original matrix. Because an irredundant covering of the binary binding matrix of system (1) corresponds to a minimal solution, only minimal solutions are generated. The disadvantage of using partitioning is that if the partitioning of the binary binding matrix contains only one component (i.e., the matrix), then benefits cannot be obtained from partitioning, and the time used to perform partitioning is wasted. The impact of partitioning on performance is discussed further in Section 6.


## 5. The Divide-and-Conquer Algorithm

We propose a divide-and-conquer algorithm for constructing the set of irredundant coverings of a binary matrixM. The algorithm follows a set of rules specified by Lin [8] either to obtain the irredundant coverings directly or to decompose a binary matrix into one or more submatrices. Rules 1–3 consider some trivial cases of M whose irredundant coverings can be directly derived and are adopted as the termination condition in the proposed algorithm.Rule 1.
IfJ is a singleton {
j
}, then Φ
(
M
)
=
{
{
i
}
∣
i
∈
I
j
(
M
)
}.Rule 2.
IfJ
=
∅, then Φ
(
M
)
=
{
∅
}.Rule 3.
If there exists a columnj
∈
J such that I
j
(
M
)
=
∅, then Φ
(
M
)
=
∅.Rule4 reduces a binary matrix by identifying the indexes of the rows that are required in all irredundant coverings of the matrix.Rule 4 (singleton removal).
If there exists a singletonI
j
(
M
)
=
{
i
} for some j
∈
J, then Φ
(
M
)
=
{
{
i
}
}
⋈
Φ
(
M
[
I
∖
{
i
}
;
J
∖
J
i
(
M
)
]
).If none of the above rules are applicable, then the algorithm calculates the partitioningΨ
(
M
). Subsequently, if |
Ψ
(
M
)
|
>
1, then the irredundant coverings of M can be derived from the irredundant coverings of those submatrices in Ψ
(
M
), according to Theorem 8. However, if |
Ψ
(
M
)
|
=
1, then Rule 5 [6] is applied to decompose M into three submatrices.Rule 5 (forced binding).
LetM
-
=
M
[
I
∖
{
i
}
;
J
∖
J
i
(
M
)
], M
+
=
M
[
I
∖
{
i
}
;
J
i
(
M
)
] and M
×
=
M
[
I
∖
{
i
}
;
J
] for some i
∈
I. Then, Φ
(
M
)
=
(
{
{
i
}
}
⋈
(
Φ
(
M
-
)
∖
Φ
(
M
+
)
)
)
⋃
Φ
(
M
×
).Algorithm1 shows the proposed algorithm (denoted as PA). Notably, this algorithm does not find any covering that is redundant. If a matrix can be partitioned into more than one submatrix, then lines 10 and 11 of the algorithm are applied to expedite the process of executing the algorithm by using the concept of partitioning. When lines 10 and 11 are excluded, the resulting algorithm, denoted as non-PA, is identical to the algorithm proposed by Markovskii [6] or Lin [8]. The PA is demonstrated in the following examples.Algorithm 1:Algorithm for finding all irredundant coverings.
Algorithm  P
A
(
M
)
Input: a binary matrixM
=
(
m
i
j
)
|
I
|
×
|
J
| with i
∈
I and j
∈
J.
Output:Φ
(
M
)
(1)
If  J is a singleton {
j
}  then
(2)
return  {
{
i
}
i
∈
I
j
(
M
)
};
(3)
If  J
=
∅  then
(4)
return  {
∅
};
(5)
If  ∃
j
∈
J such that I
j(M) = ∅  then
(6)
return  ∅;
(7)
If  there exists a singleton I
j(M) = {
i
} for some j
∈
J  then
(8)
let  M
′
∶
=
M
[
I
∖
{
i
}
;
J
∖
J
i(M)]
(9)
return  {
{
i
}
}
⋈  PA(M
′);
// singleton removal
(10)
If  Ψ(M) = {
M
1
,
M
2
,
…
,
M
p
} and p
>
1  then
(11)
return  PA(M
1)  ⋈  PA(M
2)  ⋈
⋯
⋈  PA(M
p);
// partitioning
(12)
Let  row i be the row with the most 1s in M;
(13)
Let  M
×
∶
= M[I
∖
{
i
}; J] and M
-
∶
= M[I
∖
{
i
}; J
∖
J
i(M)];
(14)
Let  Φ
(
M
-
)
∶
=  PA
(
M
-
) and Φ
(
M
×
)
∶
=  PA
(
M
×
);
(15)
Let  M
+
∶
=
M
[
I
∖
{
i
}
;
J
i
(
M
)
];
(16)
Let  Δ
∶
=
{
C
∈
Φ
(
M
-
)
C
is not a covering of
M
+
};
(17)
Return  (
{
{
i
}
}
⋈
Δ
)
⋃
‍
Φ
(
M
×
);
// forced bindingExample 9.
Consider the matrixM in Example 4. Select row 1 to apply forced binding (lines 12–17 of PA) and obtain three matrixes M
-, M
+, and M
×, as shown in
(13)
M
-
=
3
2
3
4
(
1
1
0
)
M
+
=
1
2
2
3
4
(
0
1
1
0
0
0
)
M
×
=
1
2
3
2
3
4
(
0
1
1
1
0
1
0
0
0
)
.Lines 1-2 of PA yieldΦ
(
M
-
)
=
{
{
2
}
,
{
3
}
}, and subsequently lines 15-16 yield Δ
=
Φ
(
M
-
). By lines 7–9 and then lines 1-2 of PA, we have Φ
(
M
×
)
=
{
{
2,3
}
}. Finally, Φ
(
ℳ
) = (
{
{
1
}
}
⋈
Δ
)
∪
Φ
(
M
×
) = {
{
1,2
}
,
{
1,3
}
,
{
2,3
}
}.Example 10.
Consider the matrixM in Example 7. Since Ψ
(
M
)
=
{
M
1
,
M
2
}, by Theorem 8, Φ
(
M
)
=
Φ
(
M
1
)
⋈
Φ
(
M
2
). To compute Φ
(
M
1
), we select row 4 of M
1 to apply forced binding (lines 12–17 of PA) and obtain three matrixes M
1
-, M
1
+, and M
1
× (shown below) such that Φ
(
M
1
)
=
(
{
{
4
}
}
⋈
(
Φ
(
M
1
-
)
∖
Φ
(
M
1
+
)
)
)
⋃
Φ
(
M
1
×
):
(14)
M
1
-
=
9
6
8
(
1
1
)
M
1
+
=
5
8
6
8
(
1
0
0
1
)
M
1
×
=
5
8
9
6
8
(
1
0
1
0
1
1
)
.By lines 1-2 of PA,Φ
(
M
1
-
)
=
{
{
6
}
,
{
8
}
}. By lines 7–9 and then lines 1-2 of PA, Φ
(
M
1
×
)
=
{
{
6,8
}
}. Consequently, Φ
(
M
1
)
=
{
{
4,6
}
,
{
4,8
}
,
{
6,8
}
}.To computeΦ
(
M
2
), we select row 1 of M
2 to apply forced binding and obtain three matrixes M
2
-, M
2
+, and M
2
× (shown below) such that Φ
(
M
2
)
=
(
{
{
1
}
}
⋈
(
Φ
(
M
2
-
)
∖
Φ
(
M
2
+
)
)
)
⋃
Φ
(
M
2
×
). Thus,
(15)
M
2
-
=
2
4
6
7
2
3
5
7
9
(
1
0
0
0
0
0
1
1
0
1
1
0
1
0
0
0
0
1
0
1
)
,
M
2
+
=
1
3
10
2
3
5
7
9
(
0
1
1
0
0
0
0
0
0
1
1
0
0
0
0
)
,
M
2
×
=
1
2
3
4
6
7
10
2
3
5
7
9
(
0
1
1
0
0
0
1
0
0
0
0
1
1
0
0
0
0
1
1
0
0
1
1
1
0
0
0
0
0
0
0
1
0
1
0
)
.Then,M
2
- can be further partitioned into M
3 and M
4 (shown below), and consequently Φ
(
M
2
-
)
=
Φ
(
M
3
)
⋈
Φ
(
M
4
):
(16)
M
3
=
2
2
7
(
1
1
)
M
4
=
4
6
7
3
5
9
(
0
1
1
1
1
0
1
0
1
)
.By lines 1-2 of PA,Φ
(
M
3
)
=
{
{
2
}
,
{
7
}
}. Calculating Φ
(
M
4
) is similar to calculating Φ
(
M
1
), and thus we have Φ
(
M
4
)
=
{
{
3,5
}
,
{
3,9
}
,
{
5,9
}
}. Consequently, Φ
(
M
2
-
) = {
{
2
}
,
{
7
}
}
⋈
{
{
3,5
}
,
{
3,9
}
,
{
5,9
}
} = {
{
2,3
,
5
}
,
{
2,3
,
9
}
,
{
2,5
,
9
}
,
{
3,5
,
7
}
,
{
3,7
,
9
}
,
{
5,7
,
9
}
}.M
2
× can be further partitioned into M
5 and M
6 (shown below), and consequently Φ
(
M
2
×
)
=
Φ
(
M
5
)
⋈
Φ
(
M
6
). By lines 7–9 and then lines 1-2 of PA, Φ
(
M
5
)
=
{
{
2,7
}
}. Similar to Φ
(
M
1
), Φ
(
M
6
)
=
{
{
3,5
}
,
{
3,9
}
,
{
5,9
}
}. Thus, Φ
(
M
2
×
)
=
{
{
2,3
,
5,7
}
,
{
2,3
,
7,9
}
,
{
2,5
,
7,9
}
}:
(17)
M
5
=
1
2
3
10
2
7
(
0
1
1
1
1
1
1
0
)
M
6
=
4
6
7
3
5
9
(
0
1
1
1
1
0
1
0
1
)
.Therefore,Φ
(
M
2
)
=
{
{
1,2
,
3,5
}
,
{
1,2
,
3,9
}
,
{
1,2
,
5,9
}, {
1,3
,
5,7
}, {
1,3
,
7,9
}, {
1,5
,
7,9
}, {
2,3
,
5,7
}, {
2,3
,
7,9
}, {
2,5
,
7,9
}
}. Since both Φ
(
M
1
) and Φ
(
M
2
) are found, Φ
(
M
) can be derived from Φ
(
M
1
)
⋈
Φ
(
M
2
).


## 6. Performance Study

This performance study focused on evaluating the impact of applying the concept of partitioning. This was achieved by comparing the performance of the PA with that of the non-PA, because the algorithms differed only in whether the concept of partitioning was used. As discussed in Section3, finding all of the irredundant coverings of the binary binding matrix ℳ
* is the most time-consuming step in solving system (1). Therefore, we measured only the time required to derive Φ
(
ℳ
*
) from ℳ
* to evaluate the speed at which system (1) can be solved using a given approach.


### 6.1. Test Matrices

We used binary binding matrices rather than system (1) for this performance study. This offered three advantages. First, a binary binding matrix is a binary matrix only and is independent of any specific Archimedean t-norm function. Second, using binary binding matrices prevents the imprecision caused by floating point truncation from occurring when solving system (1). Third, generating a large binary matrix is easier than generating system (1) with a high number of equations and variables.Algorithm2 shows the procedure for generating the test matrices. This procedure involves four parameters, m, n, d, and p, and generates an m
×
n binary matrix M with density d such that Ψ
(
M
) contains p submatrices of M with approximately the same number of rows and columns. Thedensity of M is defined as the number of nonzero elements in M divided by m
×
n. In this procedure, an irredundant covering is first injected into the matrix to avoid Φ
(
M
)
=
∅ (lines 5–9). Then, the elements in the regions of M that correspond to these p submatrices are repeatedly and randomly chosen to assume the value of 1 until the number of elements with a value of 1 reaches ⌈
m
*
n
*
d
⌉ (lines 11–15).Algorithm 2:Procedure for generating test matrices.
Input:m
,
n
,
d and p. Note: 1
/
m
⩽
d
⩽
1
/
p and p
⩽
n are required.
Output:M
=
(
m
i
j
)
|
I
|
×
|
J
| where i
∈
I
=
{
1
,
…
,
m
} and j
∈
J
=
{
1
,
…
,
n
}
(1)
Let  P
∶
=
{
1,2
,
…
,
p
};
(2)Randomly divide I into p disjoint subsets I
1
,
I
2
,
…
,
I
p such that ⋃
k
∈
P
‍
I
k
=
I, and |
|
I
k
^
|
-
|
I
k
˘
|
|
⩽
1 for any k
^
,
k
˘
∈
P;
(3)Randomly divide J into p disjoint subsets J
1
,
J
2
,
…
,
J
p such that ⋃
k
∈
P
‍
J
k
=
J, and |
|
J
k
^
|
-
|
J
k
˘
|
|
⩽
1 for any k
^
,
k
˘
∈
P;
(4)Initialize m
i
j to 0 for all i
∈
I and j
∈
J;
(5)
For  k
=
1 to p  do  // inject an irredundant covering to avoid Φ
(
M
)
=
∅.
(6)
For  each  j
∈
J
k  do
(7)  Randomly select i from I
k, and set m
i
j
∶
=
1;
(8)
End  of  for  each
(9)
End  of  for
(10)
Let  l
∶
=
⌈
m
*
n
*
d
⌉
-
n;
(11)
While  l
>
0  do
(12) Randomly select i and j from I and J, respectively;
(13)
If  i
∈
I
k, j
∈
J
k for some k
∈
P, and m
i
j
=
0  then
(14)  let  m
i
j
∶
=
1 and l
∶
=
l
-
1;
(15)
End  of  while
(16)
Return  M;In this study, test matrices were generated withm
=
n
=
24, p ranging from 1 to 8 and d ranging from 2
/
m to 1
/
p with an increment of 1
/
m. Notably, if d
=
1
/
m, then the matrix had at most one irredundant covering. Therefore, only test matrices with a density of no less than 2
/
m were generated in this study. In addition, when the partitioning of a matrix contains p submatrices of equal size, the density of the matrix could not be greater than 1
/
p and, thus, the greatest density was set to 1
/
p.Because this procedure is random, it does not always generate a binary matrix with numerous irredundant coverings. This is especially true whenm and n are low or d is near zero or one. Therefore, for each setting of d and p, this procedure was repeated five times to generate five test matrices. For example, when p
=
1, we varied d from 2
/
24 to 1
/
1 with an increment of 1
/
24 and consequently generated 115 (=
23
×
5) test matrices. In general, given a fixed p value, (
24
/
p
-
1
)
×
5 test matrices were generated in this study. That is, 55, 35, 25, 15, and 10 test matrices were generated for p
=
2, 3, 4, 6, and 8, respectively. For clarity, Figure 2 shows only the number of irredundant coverings of the test matrices with the lowest or the highest number of irredundant coverings among the respective five test matrices with the same p and d values. Among all the test matrices generated, the matrix with the highest number of irredundant coverings (|
Φ
(
M
)
|
=
9680) was generated using d
=
6
/
24 and p
=
3.Figure 2
Densityd versus the number of irredundant coverings |
Φ
(
M
)
|.To understand howd affects the number of irredundant coverings, we performed a preliminary check on the number of irredundant coverings for the test matrices with p
=
1. Specifically, we first grouped the generated matrices with p
=
1 by their densities. Then, for every two groups with their difference in density being 1
/
24, a Mann-Whitney U test was performed to compare the difference of the number of irredundant coverings between both groups. The results show that when both groups’ densities are less than or equal to 5
/
24, the number of irredundant coverings is smaller in the group with smaller density; when both groups’ densities are greater than or equal to 8
/
24, the number of irredundant coverings is larger in the group with smaller density; when both groups’ densities are between 5
/
24 and 8
/
24, there is no significant difference between the two groups in the number of irredundant coverings. Thus, although we did not include test matrices with density less than 2
/
24 in this study, the generated test matrices have covered a wide range of density to provide meaningful analysis.


### 6.2. Performance Results

The performance study was conducted on a desktop PC with Pentium D (3.0 GHz) processor and 1 gigabyte main memory, running Windows XP. To evaluate the impact of using partitioning, each test matrix was subjected to two tests, a test in which the PA was used and a test in which the non-PA was used. The results are shown in Figures3–5.Figure 3
|
Φ
(
M
)
| versus execution time (in ms) when p
=
1.Figure 4
|
Φ
(
M
)
| versus execution time (in ms) of non-PA when p
>
1.Figure 5
|
Φ
(
M
)
| versus execution time (in ms) of PA when p
>
1.First, consider the group of test matrices withp
=
1. Because p
=
1, the 115 test matrices in this group were generated without intentionally making them capable of being partitioned into more than one submatrix. Prior to comparing the execution times of the PA and non-PA on this group of test matrices, we used the Kolmogorov-Smirnov test to check the normality of the execution time, and the results show that the assumption of normality failed for both the PA and non-PA. Because the assumption of normality of distribution was questionable, the Wilcoxon signed-rank test was used as a substitute for a paired t-test to compare the difference between the execution time of the PA and non-PA. The results were in the expected direction and were significant (z
=
-
7.741 and p
<
0.05). Thus, it is statistically significant to say that the execution time of the PA is smaller than that of the non-PA with this group of test matrices. This may be due to the fact that, although the test matrices in this group could not be partitioned into more than one submatrix (i.e., |
Ψ
(
M
)
|
=
1), several of the submatrices could and, therefore, the concept of partitioning was still helpful. Figure 3 shows that the execution times of the PA and non-PA exhibited a similar pattern: both were linearly proportional to the square of the number of irredundant coverings of the test matrix. The correlation coefficient between the execution time and the square of the number of irredundant coverings was 0.99502 for the PA and 0.990939 for the non-PA.For test matrices in whichp
>
1, Figures 4 and 5 reveal that the PA outperformed the non-PA by more than three orders of magnitude. Figure 4 shows that the execution time of the non-PA was still linearly proportional to the square of the number of irredundant coverings and was not affected by the value of p. Figure 5 shows that, for any test matrix in which p
>
1, the PA required less than 120 ms to determine Φ
(
M
). If a test matrix can be partitioned into more than one submatrix (i.e., |
Ψ
(
M
)
|
>
1), then the PA first identifies the irredundant coverings of these submatrices. Because the number of irredundant coverings of the test matrix is the product of the number of irredundant coverings of these submatrices, finding the irredundant coverings of these submatrices is much faster than finding those of the test matrix. Consequently, the time required by the PA to find all the irredundant coverings can be reduced substantially. We also used the Wilcoxon signed-rank test to compare the execution times of the PA and non-PA on each group of test matrices with the same number of partitions. The results were all in the expected direction and were significant (z
=
-
6.452, −5.16, −4.372, −3.408, and −2.803 for the groups of test matrices with 2, 3, 4, 6, and 8 partitions, respectively, and all p
<
0.05).


## 6.1. Test Matrices

We used binary binding matrices rather than system (1) for this performance study. This offered three advantages. First, a binary binding matrix is a binary matrix only and is independent of any specific Archimedean t-norm function. Second, using binary binding matrices prevents the imprecision caused by floating point truncation from occurring when solving system (1). Third, generating a large binary matrix is easier than generating system (1) with a high number of equations and variables.Algorithm2 shows the procedure for generating the test matrices. This procedure involves four parameters, m, n, d, and p, and generates an m
×
n binary matrix M with density d such that Ψ
(
M
) contains p submatrices of M with approximately the same number of rows and columns. Thedensity of M is defined as the number of nonzero elements in M divided by m
×
n. In this procedure, an irredundant covering is first injected into the matrix to avoid Φ
(
M
)
=
∅ (lines 5–9). Then, the elements in the regions of M that correspond to these p submatrices are repeatedly and randomly chosen to assume the value of 1 until the number of elements with a value of 1 reaches ⌈
m
*
n
*
d
⌉ (lines 11–15).Algorithm 2:Procedure for generating test matrices.
Input:m
,
n
,
d and p. Note: 1
/
m
⩽
d
⩽
1
/
p and p
⩽
n are required.
Output:M
=
(
m
i
j
)
|
I
|
×
|
J
| where i
∈
I
=
{
1
,
…
,
m
} and j
∈
J
=
{
1
,
…
,
n
}
(1)
Let  P
∶
=
{
1,2
,
…
,
p
};
(2)Randomly divide I into p disjoint subsets I
1
,
I
2
,
…
,
I
p such that ⋃
k
∈
P
‍
I
k
=
I, and |
|
I
k
^
|
-
|
I
k
˘
|
|
⩽
1 for any k
^
,
k
˘
∈
P;
(3)Randomly divide J into p disjoint subsets J
1
,
J
2
,
…
,
J
p such that ⋃
k
∈
P
‍
J
k
=
J, and |
|
J
k
^
|
-
|
J
k
˘
|
|
⩽
1 for any k
^
,
k
˘
∈
P;
(4)Initialize m
i
j to 0 for all i
∈
I and j
∈
J;
(5)
For  k
=
1 to p  do  // inject an irredundant covering to avoid Φ
(
M
)
=
∅.
(6)
For  each  j
∈
J
k  do
(7)  Randomly select i from I
k, and set m
i
j
∶
=
1;
(8)
End  of  for  each
(9)
End  of  for
(10)
Let  l
∶
=
⌈
m
*
n
*
d
⌉
-
n;
(11)
While  l
>
0  do
(12) Randomly select i and j from I and J, respectively;
(13)
If  i
∈
I
k, j
∈
J
k for some k
∈
P, and m
i
j
=
0  then
(14)  let  m
i
j
∶
=
1 and l
∶
=
l
-
1;
(15)
End  of  while
(16)
Return  M;In this study, test matrices were generated withm
=
n
=
24, p ranging from 1 to 8 and d ranging from 2
/
m to 1
/
p with an increment of 1
/
m. Notably, if d
=
1
/
m, then the matrix had at most one irredundant covering. Therefore, only test matrices with a density of no less than 2
/
m were generated in this study. In addition, when the partitioning of a matrix contains p submatrices of equal size, the density of the matrix could not be greater than 1
/
p and, thus, the greatest density was set to 1
/
p.Because this procedure is random, it does not always generate a binary matrix with numerous irredundant coverings. This is especially true whenm and n are low or d is near zero or one. Therefore, for each setting of d and p, this procedure was repeated five times to generate five test matrices. For example, when p
=
1, we varied d from 2
/
24 to 1
/
1 with an increment of 1
/
24 and consequently generated 115 (=
23
×
5) test matrices. In general, given a fixed p value, (
24
/
p
-
1
)
×
5 test matrices were generated in this study. That is, 55, 35, 25, 15, and 10 test matrices were generated for p
=
2, 3, 4, 6, and 8, respectively. For clarity, Figure 2 shows only the number of irredundant coverings of the test matrices with the lowest or the highest number of irredundant coverings among the respective five test matrices with the same p and d values. Among all the test matrices generated, the matrix with the highest number of irredundant coverings (|
Φ
(
M
)
|
=
9680) was generated using d
=
6
/
24 and p
=
3.Figure 2
Densityd versus the number of irredundant coverings |
Φ
(
M
)
|.To understand howd affects the number of irredundant coverings, we performed a preliminary check on the number of irredundant coverings for the test matrices with p
=
1. Specifically, we first grouped the generated matrices with p
=
1 by their densities. Then, for every two groups with their difference in density being 1
/
24, a Mann-Whitney U test was performed to compare the difference of the number of irredundant coverings between both groups. The results show that when both groups’ densities are less than or equal to 5
/
24, the number of irredundant coverings is smaller in the group with smaller density; when both groups’ densities are greater than or equal to 8
/
24, the number of irredundant coverings is larger in the group with smaller density; when both groups’ densities are between 5
/
24 and 8
/
24, there is no significant difference between the two groups in the number of irredundant coverings. Thus, although we did not include test matrices with density less than 2
/
24 in this study, the generated test matrices have covered a wide range of density to provide meaningful analysis.


## 6.2. Performance Results

The performance study was conducted on a desktop PC with Pentium D (3.0 GHz) processor and 1 gigabyte main memory, running Windows XP. To evaluate the impact of using partitioning, each test matrix was subjected to two tests, a test in which the PA was used and a test in which the non-PA was used. The results are shown in Figures3–5.Figure 3
|
Φ
(
M
)
| versus execution time (in ms) when p
=
1.Figure 4
|
Φ
(
M
)
| versus execution time (in ms) of non-PA when p
>
1.Figure 5
|
Φ
(
M
)
| versus execution time (in ms) of PA when p
>
1.First, consider the group of test matrices withp
=
1. Because p
=
1, the 115 test matrices in this group were generated without intentionally making them capable of being partitioned into more than one submatrix. Prior to comparing the execution times of the PA and non-PA on this group of test matrices, we used the Kolmogorov-Smirnov test to check the normality of the execution time, and the results show that the assumption of normality failed for both the PA and non-PA. Because the assumption of normality of distribution was questionable, the Wilcoxon signed-rank test was used as a substitute for a paired t-test to compare the difference between the execution time of the PA and non-PA. The results were in the expected direction and were significant (z
=
-
7.741 and p
<
0.05). Thus, it is statistically significant to say that the execution time of the PA is smaller than that of the non-PA with this group of test matrices. This may be due to the fact that, although the test matrices in this group could not be partitioned into more than one submatrix (i.e., |
Ψ
(
M
)
|
=
1), several of the submatrices could and, therefore, the concept of partitioning was still helpful. Figure 3 shows that the execution times of the PA and non-PA exhibited a similar pattern: both were linearly proportional to the square of the number of irredundant coverings of the test matrix. The correlation coefficient between the execution time and the square of the number of irredundant coverings was 0.99502 for the PA and 0.990939 for the non-PA.For test matrices in whichp
>
1, Figures 4 and 5 reveal that the PA outperformed the non-PA by more than three orders of magnitude. Figure 4 shows that the execution time of the non-PA was still linearly proportional to the square of the number of irredundant coverings and was not affected by the value of p. Figure 5 shows that, for any test matrix in which p
>
1, the PA required less than 120 ms to determine Φ
(
M
). If a test matrix can be partitioned into more than one submatrix (i.e., |
Ψ
(
M
)
|
>
1), then the PA first identifies the irredundant coverings of these submatrices. Because the number of irredundant coverings of the test matrix is the product of the number of irredundant coverings of these submatrices, finding the irredundant coverings of these submatrices is much faster than finding those of the test matrix. Consequently, the time required by the PA to find all the irredundant coverings can be reduced substantially. We also used the Wilcoxon signed-rank test to compare the execution times of the PA and non-PA on each group of test matrices with the same number of partitions. The results were all in the expected direction and were significant (z
=
-
6.452, −5.16, −4.372, −3.408, and −2.803 for the groups of test matrices with 2, 3, 4, 6, and 8 partitions, respectively, and all p
<
0.05).


## 7. Conclusion

In a system of fuzzy relational equations with numerous variables and equations, several variables and equations are likely to be unrelated, and when such a situation occurs, partitioning can be used to facilitate substantial reduction of the time required to determine all the minimal solutions. Therefore, considering partitioning when solving fuzzy relational equations is crucial.Partitioning is not useful when all of the rows and columns of a binary binding matrixM are related, and after applying forced binding (Rule 5 in Section 5) to derive two submatrices M
× and M
-, all of the rows and columns of both submatrices are still related. Intuitively, this situation occurs as the density of M approaches one (i.e., d is near 1 and p
=
1, as shown in Figure 2). In this situation, the problem contains considerably fewer irredundant coverings, as shown in Figure 2, and, thus, can be solved efficiently with or without considering partitioning.In addition to max-Archimedeant-norm fuzzy relational equations, numerous types of fuzzy relational equations have been demonstrated to be equivalent to the set covering problem [12]. The partitioning concept and the divide-and-conquer approach discussed in this paper can also be applied to these fuzzy relational equations with little modification.Instead of generating test matrices (as in Algorithm2), Hu and Fang [13] proposed procedures for generating test problems with various characteristics for use in max-t-norm fuzzy relational equations, with t being the min, product, or the Łukasiewicz t-norm. Because both the product and Łukasiewicz t-norm are Archimedean t-norms, test problems generated by conducting the related procedures can be used in future studies to evaluate the performance of the proposed method further.



---

*Source: 315290-2014-05-11.xml*