On the minimal solution for max-product fuzzy relation inequalities

1.   Introduction

The fuzzy relation inequality is a concept in fuzzy set theory that generalizes the notion of inequality from classical mathematics to the context of fuzzy sets. In classical mathematics, inequality is a binary relation between two elements that describes the order or magnitude relationship between them. However, in fuzzy set theory, where membership degrees quantify uncertainty, the notion of inequality must be broadened.

In fuzzy set theory, a fuzzy relation is defined as a mapping from a Cartesian product of two sets to the unit interval $[0, 1]$. It indicates a degree of compatibility or similarity between elements of the two sets. A fuzzy relation inequality refers to a comparison of two fuzzy relations in terms of their membership degrees.

To understand fuzzy relation inequalities, it is important to grasp the concept of composition of fuzzy relations. The composition of two fuzzy relations combines their degrees of compatibility or similarity to produce a new fuzzy relation. The commonly used composition in the fuzzy relation equations or inequalities is the max-t-norm. There are three elementary types of continuous t-norm, i.e., minimum (min), product, and Łukasiewicz t-norm. The existence conditions for the max-t-norm composition were presented in ^[1]. The first studied was the max-min composition in a fuzzy relation system ^[2]. However, it was later discovered that the max-product one would be more suitable for some specific situations ^[3,4]. The investigation of the max-product fuzzy relation equations would be traced back to ^[5].

Whether it is an equations system or an inequalities system, the fuzzy relation system composed by max-product composition could be completely solved ^[4,6,7]. Its complete solution set was generated by a maximum solution and a finite number of minimal solutions ^[8]. Deriving all its minimal solutions is equivalent to an NP-hard problem (exactly the set covering problem) ^[9]. The number of minimal solutions increases exponentially associated with the number of variables and equations (or inequalities) ^[7,8]. As presented in ^[4], the proposed resolution approach should eliminate the non-minimal solution for obtaining the complete set of minimal solutions. As a consequence, the method for checking whether a solution is minimal becomes crucial in this procedure.

Since there may exist exponentially many minimal solutions, it can be difficult or even unnecessary to find out all minimal solutions. Instead of solving all the minimal solutions, it is often more practical to obtain some specific minimal solutions in some particular situations, such as the lexicographic minimal solution ^[10] and the minimal solution with an upper bound ^[11,12]. In these cases, it is also important to check whether a solution is indeed minimal.

In fact, regarding the max-product fuzzy relation inequalities, one of the hottest research topics is the associated optimization problems ^[13,14,15]. For most of the linear optimization problems subject to the max-product fuzzy relation inequalities, there exists a minimal solution such that it is exactly an optimal solution of the optimization problem ^[16]. As a result, one could find the optimal solution by selecting it from the set of all minimal solutions, or quasi-minimal solutions ^[17,18,19].

The famous t-norms and s-norms (or, say, t-conorms, the dual norms of t-norms) were fully discussed in ^[20,21,22]. The authors investigated some important properties of two kinds of triangular norms. There were several kinds of classical t-norms, including minimum ($\wedge$), product ($\cdot$), Łukasiewicz $T_{\mboxŁ}$ and the Yager t-norm. It is well known that the minimum operator and the product operator are two commonly used t-norms, due to their wide application. These composed operators play a key role in the fuzzy relation systems, including the inequalities system and equations system ^[23,24,25].

Regarding the FRSs, there were two major research topics, i.e., (i) solving the complete solution set of the FRS and (ii) solving the optimal solution of the optimization problems subject to the FRS ^[24]. Both these two research topics require the set of all minimal solutions. For the topic in (i), the minimal solution set is indispensable due to the structure of the complete solution set. It is well known that the solution set $S$ for an FRS with max-t-norm composition could be written as ^[23,26]

where $\check{S}$ represents the set of all minimal solutions, while $\hat{x}$ is the maximum solution. In Eq (1.1), the minimal solution set $\check{S}$ could also be replaced by the set of all quasi-minimal solutions.

On the other hand, for the topic in (ii), the minimal solution set also plays a key role ^[27,28,29]. For the optimization problems subject to an FRS, the optimal solution was obtained by selecting in the set of all minimal solutions ^[30,31,32] or quasi-minimal solutions ^[33,34,35], or was generated by a series of sub-problems derived by all the minimal solutions ^[36,37,38].

As a consequence, solving the minimal solution set is important in the investigation on the FRS. Then another problem arises, which is how to obtain the minimal solution set. Unfortunately, as pointed out in ^[7,10,39], for the fuzzy relation inequalities system with max-product composition, it is incapable of computing all the minimal solutions directly. Hence, in this work we aim to propose an effective approach for checking whether a vector (or a quasi-minimal solution) is a minimal solution. This approach enables us to find the minimal solution set with a lower computational complexity.

In this work, we aim to address the problem of checking whether a solution is minimal in the system of max-product fuzzy relation inequalities. We structure the remainder of our work as follows: Section 2 provides some preliminaries on the max-product system. The major content is set in Section 3, in which we develop the approach for checking whether a given solution is minimal. An illustrative example is included in Section 4. In Section 5, we further discuss our proposed checking approach by comparing it to some existing works. Finally, Section 6 presents the conclusion.

2.   Max-product fuzzy relation inequalities

In this section, we present the max-product fuzzy relation inequalities and their related existing concepts and results. The max-product fuzzy relation inequalities have been studied in ^[7,23,40].

In ^[7], the following max-product fuzzy relation inequalities were introduced for describing the system of wireless communication emission base stations:

in which $\alpha_{ij}, x_{j}\in [0, 1]$, $\beta_{i}\in(0, 1]$, and

Here $\mathcal{M}$ and $\mathcal{N}$ are two index sets; "$\vee$" means the maximum operation. The matrix form of (2.1) is usually denoted by

with $\alpha = (\alpha_{ij})_{i\in \mathcal{M}, j\in \mathcal{N}}$, $x = (x_{j})_{j\in \mathcal{N}}$, $\beta = (\beta_{i})_{i\in \mathcal{M}}$. Following the formulae in (2.2), we could characterize the complete solution set of (2.1) or (2.2) as follows:

Definition 1. ^[23,40] We say system (2.1) is consistent if $\mathcal{S}(\alpha, \beta)\neq\emptyset$. Otherwise, it is said to be inconsistent.

Definition 2. ^[23,40] Let $\tilde{x}\in \mathcal{S}(\alpha, \beta)$ be a solution for (2.1). If $\tilde{x}\geq x$ for any $x\in \mathcal{S}(\alpha, \beta)$, we say $\tilde{x}$ a minimal solution. If for any $x\in \mathcal{S}(\alpha, \beta)$, $x\leq\tilde{x}$ indicates $x = \tilde{x}$, we say $\tilde{x}$ a maximum solution.

Let

Theorem 1 below, presented in ^[7], is used to verify the consistency of (2.1) using the vector $\hat{x}$ introduced above.

Theorem 1. ^[23,40] System (2.1) is consistent iff $\hat{x}\in \mathcal{S}(\alpha, \beta)$. Moreover, when system (2.1) is consistent, $\hat{x}$ serves as the maximum solution.

In addition, we provide some related properties on system (2.1) as follows:

Proposition 1. ^[23,40] Let $x\in \mathcal{S}(\alpha, \beta)$ be a solution. Then $x'$ is also a solution, for any $x'\in [x, \hat{x}]$.

Proposition 2. ^[23,40] Let $x', x''\in \mathcal{S}(\alpha, \beta)$ be two solutions. Then $x'\vee x''$ is also a solution.

If we denote the set of all minimal solutions by $\check{\mathcal{S}}(\alpha, \beta)$, then the complete solution set of (2.1) can be represented in the form presented in Theorem 2 below.

Theorem 2. ^[23,40] The complete solution set to system (2.1) is

3.   How to check whether a solution is minimal in the solution set $\mathcal{S}(\alpha, \beta)$

In this section, we always assume that $y = (y_{1}, \cdots, y_{n})$ is a given solution in system (2.1), i.e., $y\in\mathcal{S}(\alpha, \beta)$. We aim to propose an effective method for checking whether the solution $y$ is a minimal solution.

3.1.   Properties on three index sets

Based on the given solution $y$, we first denote the following index sets:

Moreover, if $\mathcal{M}^{ = }\neq\emptyset$, we further set

for any $i\in\mathcal{M}^{ = }$.

Next, we investigate some relevant properties on the above three index sets.

Proposition 3. If $y$ is minimal in $\mathcal{S}(\alpha, \beta)$, then there should be $\mathcal{N}^{+}\neq\emptyset$ and $\mathcal{M}^{ = }\neq\emptyset$.

Proof. (i) It is self-evident $y\in\mathcal{S}(\alpha, \beta)$. Taking arbitrarily $i\in \mathcal{M}$, we have

according to system (2.1). Since $\alpha_{ij}\in [0, 1]$ and $\beta_{i} > 0$, there exists $j'\in \mathcal{N}$ such that

That is $j'\in \mathcal{N}^{+}$ by (3.1). Thus $\mathcal{N}^{+}\neq\emptyset$.

(ii) (By contradiction) Assume that $\mathcal{M}^{ = } = \emptyset$. Then by (3.2) and (3.4),

Denote $\Upsilon = \bigwedge\limits_{i\in \mathcal{M}}(\bigvee\limits_{j\in \mathcal{N}}\alpha_{ij}y_{j} - \beta_{i})$. Then it is clear that $\Upsilon > 0$.

Let $j^{+}\in N^{+}$ be an arbitrary index in $N^{+}$. Then by (3.1), $y_{j^{+}} > 0$. Define $y' = (y'_{1}, \cdots, y'_{n})$ by

It is clear that $y'\in [0, 1]^{n}$. Moreover, since $\Upsilon > 0$ and $y_{j^{+}} > 0$, we have

According to (3.7), it also holds that $y'_{j} \leq y_{j}$, $\forall j\in \mathcal{N}$. This shows that $y'\leq y$ and $y'\neq y$.

Next, we check that $y'\in \mathcal{S}(\alpha, \beta)$. Take arbitrarily $l\in \mathcal{M}$. We have

Case 1. If $\alpha_{lj^{+}}y_{j^{+}} = \bigvee\limits_{j\in \mathcal{N}}\alpha_{lj}y_{j}$, then

Case 2. If $\alpha_{lj^{+}}y_{j^{+}}\neq\bigvee\limits_{j\in \mathcal{N}}\alpha_{lj}y_{j}$, i.e., $\alpha_{lj^{+}}y_{j^{+}} < \bigvee\limits_{j\in \mathcal{N}}\alpha_{lj}y_{j}$, then there exists $j'\in \mathcal{N}$ such that $j'\neq j^{+}$ and $\alpha_{lj'}y_{j'} = \bigvee\limits_{j\in \mathcal{N}}\alpha_{lj}y_{j}$. By (3.6), we have $\alpha_{lj'}y_{j'} = \bigvee\limits_{j\in \mathcal{N}}\alpha_{lj}y_{j} > \beta_{l}$. Since $j'\neq j^{+}$, it follows from (3.7) that $y'_{j'} = y_{j'}$. As a result,

Combining Cases 1 and 2, we have $\bigvee\limits_{j\in \mathcal{N}}\alpha_{lj}y'_{j} \geq \beta_{l}$, $\forall l\in \mathcal{M}$. Hence $y'\in \mathcal{S}(\alpha, \beta)$. However, it has been proved above that $y'\leq y$ and $y'\neq y$. This leads to a contradiction since $y$ is minimal in $\mathcal{S}(\alpha, \beta)$. □

Proposition 4. Let $y$ be minimal in $\mathcal{S}(\alpha, \beta)$. Then we have $\mathcal{N}_{i}\neq\emptyset$, for any $i\in\mathcal{M}^{ = }$. Moreover, it always holds that $\bigcup\limits_{i\in\mathcal{M}^{ = }} \mathcal{N}_{i} \subseteq \mathcal{N}^{+}$.

Proof. Take any index $i\in\mathcal{M}^{ = }$. It follows from (3.2) that $\alpha_{i1}y_{1}\vee\alpha_{i2}y_{2}\vee\cdots\vee\alpha_{in}y_{n} = \beta_{i}$. There exists $j'\in \mathcal{N}$ such that

Hence $j'\in \mathcal{N}_{i}\neq\emptyset$.

Arbitrarily choose $i\in\mathcal{M}^{ = }$ and $j\in \mathcal{N}_{i}$. By (3.3), we have $\alpha_{ij}y_{j} = \beta_{i}$. Considering the given condition that $\alpha_{ij}, y_{j}\in [0, 1]$ and $\beta_{i}\geq 0$, we further get $y_{j}\geq\alpha_{ij}y_{j} = \beta_{i} > 0$. Hence $j\in \mathcal{N}^{+}$ by (3.1). This means $\mathcal{N}_{i}\subseteq\mathcal{N}^{+}$ for arbitrary $i\in\mathcal{M}^{ = }$, i.e., $\bigcup\limits_{i\in\mathcal{M}^{ = }} \mathcal{N}_{i} \subseteq \mathcal{N}^{+}$. □

3.2.   Necessity and sufficiency for checking a minimal solution using the above index sets

Let $\Delta = \Delta_{1}\wedge\Delta_{2}$, where

Proposition 5. Suppose $\Delta$ is defined as (3.12). Then we have $\Delta > 0$.

Proof. Since $y\in \mathcal{S}(\alpha, \beta)$ is a solution, according to system (2.1), it holds

Furthermore, according to (3.2), we have

i.e., $\bigvee\limits_{j\in \mathcal{N}}\alpha_{ij}y_{j} -\beta_{i} > 0, \; \; \forall i\in \mathcal{M}-\mathcal{M}^{ = }$. Thus, $\Delta_{2} = \bigwedge\limits_{i\in \mathcal{M}-\mathcal{M}^{ = }} (\bigvee\limits_{j\in \mathcal{N}}\alpha_{ij}y_{j} -\beta_{i}) > 0$.

On the other hand, according to (3.1), it is evident $y_{j} > 0$, $\forall j\in \mathcal{N}^{+}$. As a consequence, $\Delta_{1} = \bigwedge\limits_{j\in \mathcal{N}^{+}} y_{j} > 0$ and $\Delta = \Delta_{1}\wedge\Delta_{2} > 0$. □

Take an arbitrary index $j^{+}$ in $\mathcal{N}^{+}$, i.e., $j^{+}\in\mathcal{N}^{+}$. Applying the above-obtained number $\Delta$, we construct a vector $y^{-\Delta} = (y^{-\Delta}_{1}, y^{-\Delta}_{2}, \cdots, y^{-\Delta}_{n})$ as below.

Proposition 6. Suppose $y^{-\Delta}$ is defined as (3.13). Then we have $y^{-\Delta}\in [0, 1]^{n}$. Moreover, for any $i\in\mathcal{M}-\mathcal{M}^{ = }$, it holds that

Proof. (i) To prove $y^{-\Delta}\in [0, 1]^{n}$, we have to verify $y^{-\Delta}_{j}\in [0, 1]$, for any $j\in \mathcal{N}$.

If $j\neq j^{+}$, then by (3.13), $y^{-\Delta}_{j} = y_{j}\in [0, 1]$. If $j = j^{+}$, then $y^{-\Delta}_{j^{+}} = y_{j^{+}}-\Delta$. Note that $\Delta = \Delta_{1}\wedge\Delta_{2}$ and $\Delta_{1} = \bigwedge\limits_{j\in \mathcal{N}^{+}} y_{j}$. Since $j^{+}\in \mathcal{N}^{+}$, it is obvious

Hence, $y^{-\Delta}_{j^{+}} = y_{j^{+}}-\Delta \geq0$. On the other hand, since $\Delta > 0$ according to Proposition 5, it also holds $y^{-\Delta}_{j^{+}} = y_{j^{+}}-\Delta \leq y_{j^{+}} \leq 1$. Thus $y^{-\Delta}_{j^{+}}\in [0, 1]$.

(ii) Since $y\in \mathcal{S}(\alpha, \beta)$, we have

Take an arbitrary indicator $i'\in\mathcal{M}-\mathcal{M}^{ = }$.

Case 1. If $\alpha_{i'j^{+}}y_{j^{+}} = \bigvee\limits_{j\in \mathcal{N}}\alpha_{i'j}y_{j}$, then by (3.12),

Hence, $\Delta_{2}\leq \bigvee\limits_{j\in \mathcal{N}}\alpha_{i'j}y_{j} -\beta_{i'}$. So we further have

Case 2. If $\alpha_{i'j^{+}}y_{j^{+}}\neq\bigvee\limits_{j\in \mathcal{N}}\alpha_{i'j}y_{j}$, there should be $\alpha_{i'j'}y_{j'} = \bigvee\limits_{j\in \mathcal{N}}\alpha_{i'j}y_{j}$ for some $j'\in \mathcal{N}$ with $j'\neq j^{+}$. By (3.13) and (3.15),

□

Proposition 7. For $i\in\mathcal{M}^{ = }$, we have

(i) if there exists $k\in \mathcal{N}$ with $k\notin \mathcal{N}_{i}$, then $\bigvee\limits_{j\neq k} \alpha_{ij}y_{j} = \beta_{i}$,

(ii) if $|\mathcal{N}_{i}|\geq 2$, then for any $k\in \mathcal{N}_{i}$, $\bigvee\limits_{j\neq k} \alpha_{ij}y_{j} = \beta_{i}$.

Proof. (i) For $i\in\mathcal{M}^{ = }$, by (3.2) it holds

Thus, either $\bigvee\limits_{j\neq k} \alpha_{ij}y_{j} = \beta_{i}$ or $\alpha_{ik}y_{k} = \beta_{i}$ holds. Since $k\notin \mathcal{N}_{i}$, we have $\alpha_{ik}y_{k} \neq\beta_{i}$ according to (3.3). Thus there should be $\bigvee\limits_{j\neq k} \alpha_{ij}y_{j} = \beta_{i}$.

(ii) For $k\in \mathcal{N}_{i}$, we can find another index $l\in \mathcal{N}_{i}$ with $l\neq k$, since $|\mathcal{N}_{i}|\geq 2$. According to (3.3), it holds $\alpha_{il}y_{l} = \beta_{i}$. Thus

On the other hand, according to (3.18), we also have

By (3.19) and (3.20), we find $\bigvee\limits_{j\neq k} \alpha_{ij}y_{j} = \beta_{i}$. □

Theorem 3. (Necessary condition) In system (2.1), if $y$ is a minimal solution, then for any $j\in \mathcal{N}^{+}$, there is $i\in \mathcal{M}^{ = }$, such that $\mathcal{N}_{i} = \{j\}$.

Proof. (By contradiction) Assume that there exists a $j^{+}\in \mathcal{N}^{+}$, such that for any $i\in \mathcal{M}^{ = }$, it holds that $\mathcal{N}_{i}\neq\{j^{+}\}$. Note that $\mathcal{N}_{i}\neq\{j^{+}\}$ is equivalent to either

or

holds.

Based on the above index $j^{+}$ and the number $\Delta = \Delta_{1}\wedge\Delta_{2}$ defined in (3.12), we construct the corresponding vector $y^{-\Delta} = (y^{-\Delta}_{1}, y^{-\Delta}_{2}, \cdots, y^{-\Delta}_{n})$ by (3.13). We first check $y^{-\Delta}\in \mathcal{S}(\alpha, \beta)$. Suppose $i'\in \mathcal{M}$ is an arbitrary index in $\mathcal{M}$.

Case 1. When $i'\notin \mathcal{M}^{ = }$, it follows from Proposition 6 that

Case 2. When $i'\in \mathcal{M}^{ = }$, we have either "$j^{+}\notin\mathcal{N}_{i'}$" or "$j^{+}\in\mathcal{N}_{i'}$ and $|\mathcal{N}_{i'}|\geq2$" by (3.21) and (3.22). If $j^{+}\notin\mathcal{N}_{i'}$, then by (i) in Proposition 7, we have $\bigvee\limits_{j\neq j^{+}} \alpha_{i'j}y_{j} = \beta_{i'}$. If $j^{+}\in\mathcal{N}_{i'}$ and $|\mathcal{N}_{i'}|\geq2$, then by (ii) in Proposition 7, we still have $\bigvee\limits_{j\neq j^{+}} \alpha_{i'j}y_{j} = \beta_{i'}$. Observing (3.13), it is clear $y^{-\Delta}_{j} = y_{j}$ for any $j\neq j^{+}$. Hence,

Cases 1 and 2 imply that $\alpha_{i'1}y^{-\Delta}_{1}\vee\alpha_{i'2}y^{-\Delta}_{2}\vee\cdots\vee\alpha_{i'n}y^{-\Delta}_{n} \geq \beta_{i'}$, $\forall i'\in \mathcal{M}$. Hence $y^{-\Delta}\in \mathcal{S}(\alpha, \beta)$, i.e., $y^{-\Delta}$ is a solution of system (2.1). However, since $\Delta > 0$ as proved in Proposition 5, it could be easily checked that $y^{-\Delta}\leq y$ and $y^{-\Delta}\neq y$ according to (3.13). This is in conflict with the given condition that $y$ is a minimal solution. □

Take arbitrarily $k\in \mathcal{N}$. Define a related vector $y^{k, p} = (y^{k, p}_{1}, \cdots, y^{k, p}_{n})$ as

where $p\in[0, 1]$ is a given number.

Proposition 8. For $k\in \mathcal{N}$, if $k\notin \mathcal{N}^{+}$, then we have $y^{k, p}\notin \mathcal{S}(\alpha, \beta)$ for any $p < y_{k}$.

Proof. $y\in \mathcal{S}(\alpha, \beta)$ indicates $y_{j}\geq0$, $\forall j\in \mathcal{N}$. According to (3.1), $k\notin \mathcal{N}^{+}$ indicates $y_{k} = 0$. Hence $y^{k, p}_{k} = p < y_{k} = 0$. So we have $y^{k, p}\notin \mathcal{S}(\alpha, \beta)$ for any $p < y_{k}$. □

Proposition 9. For $k\in \mathcal{N}^{+}$, if there exists $i\in \mathcal{M}^{ = }$, such that $\mathcal{N}_{i} = \{k\}$, then we have $y^{k, p}\notin \mathcal{S}(\alpha, \beta)$ for any $p < y_{k}$.

Proof. Since $i\in \mathcal{M}^{ = }$, it holds

For arbitrary $j\in \mathcal{N}$ with $j\neq k$, it turns out to be $j\notin \mathcal{N}_{i}$ since $\mathcal{N}_{i} = \{k\}$. By (3.3), $\alpha_{ij}y_{j}\neq \beta_{i}$. On the other hand, by (3.26), $j\in \mathcal{N}$ indicates $\alpha_{ij}y_{j}\leq\alpha_{i1}y_{1}\vee\alpha_{i2}y_{2}\vee\cdots\vee\alpha_{in}y_{n} = \beta_{i}$. So we have

For $j = k\in \{k\} = \mathcal{N}_{i}$, by (3.3) we have $\alpha_{ik}y_{k} = \beta_{i}$. Since $\beta_{i} > 0$, it is obvious $\alpha_{ik} > 0$. Hence, $p < y_{k}$ implies

Considering (3.25), (3.27), and (3.28), we have

As a result, $y^{k, p}$ is not a solution, i.e., $y^{k, p}\notin \mathcal{S}(\alpha, \beta)$. □

Theorem 4. (Sufficient condition) In system (2.1), let $y$ be a solution. If for any $j\in \mathcal{N}^{+}$, there exists $i\in \mathcal{M}^{ = }$, such that $\mathcal{N}_{i} = \{j\}$, then $y$ should be a minimal solution.

Proof. (By contradiction) Assume that $y$ is not a minimal solution. Then there exists a solution $y'\in \mathcal{S}(\alpha, \beta)$ such that

Thus, $y'_{j}\leq y_{j}$, $\forall j\in \mathcal{N}$, and there is $k\in \mathcal{N}$ such that

Let

Based on $k, p$, and $y$, construct the vector $y^{k, p}$ following (3.25). Then we have

and $y^{k, p}_{j} = y_{j}\geq y'_{j}$, $\forall j\in \mathcal{N}$, and $j\neq k$. Hence $y^{k, p} \geq y'$. It follows from Proposition 1 that $y^{k, p}\in \mathcal{S}(\alpha, \beta)$, since $y'\in \mathcal{S}(\alpha, \beta)$.

On the other hand, next we will prove that $y^{k, p}\notin \mathcal{S}(\alpha, \beta)$, considering $k$ in two cases.

Case 1. If $k\notin \mathcal{N}^{+}$, then by Proposition 8, we have $y^{k, p}\notin \mathcal{S}(\alpha, \beta)$ since $p < y_{k}$.

Case 2. If $k\in \mathcal{N}^{+}$, according to the given condition, there exists $i\in \mathcal{M}^{ = }$ such that $\mathcal{N}_{i} = \{j\}$. Following Proposition 8, we have $y^{k, p}\notin \mathcal{S}(\alpha, \beta)$ since $p < y_{k}$.

As a consequence, whatever the value of $k$ takes, we always have $y^{k, p}\notin \mathcal{S}(\alpha, \beta)$. This is in conflict with the above-obtained result that $y^{k, p}\in \mathcal{S}(\alpha, \beta)$. □

Theorem 5. (Sufficient and necessary condition) In system (2.1), let $y$ be a solution. Then $y$ is a minimal solution if and only if for any $j\in \mathcal{N}^{+}$, there exists $i\in \mathcal{M}^{ = }$, such that $\mathcal{N}_{i} = \{j\}$.

Proof. The proof is self-evident, following the results in Theorems 3 and 4. □

4.   Illustrative example

In this section, we provide a numerical example for illustrating our proposed checking approach indicated in Theorem 5.

Example 1. Assume that there is a system of max-product fuzzy relation inequalities as follows:

Now we provide three given solutions for the above system (4.1) as

Check whether $y^{1}, y^{2}, y^{3}$ is a minimal solution, respectively.

Solution. For $y^{1} = (0, 0, 0.7, 0, 0.8)$, it is clear $\mathcal{N}^{+} = \{3, 5\}$ by (3.1). Since

according to (3.2), we find $\mathcal{M}^{ = } = \emptyset$. Following Proposition 3, it could be concluded that $y^{1} = (0, 0, 0.7, 0, 0.8)$ is not a minimal solution.

For $y^{2} = (0.5, 1, 0, 0.6, 0)$, it is clear $\mathcal{N}^{+} = \{1, 2, 4\}$ by (3.1). Since

according to (3.2), we find $\mathcal{M}^{ = } = \{1, 3, 4, 5\}$. For $i = 1$, by (3.3), we find $\mathcal{N}_{1} = \{4\}$. In a similar way, we also find $\mathcal{N}_{3} = \{1\}$, $\mathcal{N}_{4} = \{2\}$, and $\mathcal{N}_{5} = \{1, 2\}$. Note that $\mathcal{N}^{+} = \{1, 2, 4\}$. So we have

Following Theorem 5, it could be concluded that $y^{2} = (0.5, 1, 0, 0.6, 0)$ is a minimal solution.

For $y^{3} = (0.5, 0, 0, 0.6, 0.65)$, it is clear $\mathcal{N}^{+} = \{1, 4, 5\}$ by (3.1). Since

according to (3.2), we find $\mathcal{M}^{ = } = \{1, 3, 5\}$. For $i = 1$, by (3.3), we find $\mathcal{N}_{1} = \{4\}$. In a similar way, we also find $\mathcal{N}_{3} = \{1\}$ and $\mathcal{N}_{5} = \{1\}$. Note that $\mathcal{N}^{+} = \{1, 4, 5\}$. For $j = 5\in \mathcal{N}^{+}$, it is found that there does not exist any $i\in \mathcal{M}^{ = }$ such that $\mathcal{N}_{i} = \{5\}$. Following Theorem 5, it could be concluded that $y^{3} = (0.5, 0, 0, 0.6, 0.65)$ is not a minimal solution.

5.   Discussion on our proposed checking approach

5.1.   The merits of our proposed checking approach by comparing to the existing works

5.1.1.   Avoid redundant subsets in the complete solution set

In the existing works, there were several feasible methods for obtaining the complete solution set to system (2.1) ^{[7,10,24,39,41,42,43,44]}, e.g., the solution-matrix approach ^[7,10] and the FRI path approach in ^[44]. All these methods were not able to compute the minimal solution set directly. They were just capable of computing the quasi-minimal solutions. Based on the set of all quasi-minimal solutions, the complete solution set could be characterized (see in [41, Theorem 2.7] and in [44, Theorem 2.8]). The approach presented in ^[41,44] might produce some redundant subsets in representing the complete solution set. We list the following Example 2 to illustrate this situation.

Example 2. Consider the max-product fuzzy relation inequalities as follows:

We aim to obtain the complete solution set to the above system (5.1).

Using the formula in Definition 2.4 in ^[44] as follows,

we have

since $\hat{x} = (1, 1, 1, 1)$ for system (5.1). According to Eq (5.3), it is easy to find the index sets as

So, we obtain $G = G_{1}\times G_{2}\times G_{3} = \{1, 2, 3, 4\}\times \{2, 3, 4\}\times \{1, 3, 4\}$. It is clear that $G$ has 36 elements, i.e., $|G| = 36$. As a result, following Definition 2.5 in ^[44], one is able to calculate 36 quasi-minimal solutions of system (5.1). Here we omit the calculation process. For each path $e\in G$, suppose the quasi-minimal solution corresponding to $e$ is denoted by $e_{x}$. Then, by Theorem 2.7 in ^[44], the solution set of (5.1) is

The above solution set $S^{1}$ is composed by 36 subsets, induced by 36 quasi-minimal solutions (as shown in Table 1). Among these subsets, there are some redundant subsets, which could be deleted without changing the solution set $S^{1}$. For example, since

we have $[e_{x}^{2}, \hat{x}]\subseteq[e_{x}^{1}, \hat{x}]$. Thus, the subset $[e_{x}^{2}, \hat{x}]$ is redundant in the union set (5.4).

The method proposed in this work could be used to check the minimality of a quasi-minimal solution. As a result, the non-minimal solution will be deleted from the quasi-minimal solution set. By this way, one could avoid the redundant subsets in characterizing the complete solution set.

5.1.2.   Reduce computational complexity in deriving the complete solution set

For removing the redundant subsets in the complete solution set of (2.1), the pair-wise comparison method was adopted in ^{[7,10,24,39,42,43]}. In these existing works, the minimal solutions were selected from the quasi-minimal solution set by pair-wise comparison. Furthermore, the complete solution set was generated by the minimal solutions without redundant subsets.

In this work, we propose the approach for checking whether a given solution is a minimal one. Applying this checking approach, the minimal solutions could also be obtained from the quasi-minimal solution set.

In fact, the pair-wise comparison method will cause the computation of factorial growth. However, using our proposed checking approach, it just costs a polynomial computation complexity to derive the minimal solutions from the quasi-minimal solution set. In other words, our proposed checking approach will reduce the computational complexity in deriving the minimal solution set.

To reveal the computational complexities of the pair-wise comparison method and our proposed checking approach in deriving the minimal solution set, we make the following assumption for system (2.1).

$m$: The number of inequalities in (2.1).

$n$: The number of variables in (2.1).

$p$: The number of quasi-minimal solutions.

Then the pair-wise comparison method costs $n(p-1)!$ operations for deleting the non-minimal solutions in the quasi-minimal solution set. However, using our proposed checking approach, it will cost $p(5mn+n)$ operations totally.

As the size of the problem increases and the number of quasi-minimal solutions grows, $n(p-1)!$ is much more than $p(5mn+n)$. Hence, by replacing the commonly used pair-wise comparison method with our proposed checking approach, the computation complexity will drop sharply. Next, we use the system (5.1) in Example 2 to illustrate the comparison of the computation complexity.

Example 3. Continue to consider system (5.1) in Example 2. Compute the minimal solutions of (5.1) and characterize its solution set based on these minimal solutions.

As pointed out in Example 2, system (5.1) has 36 quasi-minimal solution. Using the pair-wise comparison method to delete the non-minimal solution in the quasi-minimal solution set costs $n(p-1)! = 4\cdot 35!$ operations. However, using our proposed checking approach, it only costs $p(5mn+n) = 36\cdot(5\cdot3\cdot4+4) = 2304$. Obviously, $4\cdot 35!$ is much bigger than 2304. Our proposed checking approach reduces $4\cdot 35!-2304$ operations.

After calculation, there are 9 minimal solutions, as shown in Table 2. The solution set is

5.1.3.   Reduce computational complexity in solving the fuzzy relation optimization problems

In the references ^{[31,32,33,34,35,44]}, the optimal solutions of the optimization problems subject to the FRS were derived by selecting them from the quasi-minimal solution set. The selection process was implemented by pair-wise comparison on the objective value of the quasi-minimal solutions. If we compute the minimal solution set using our proposed checking approach before implementing the selection process, then the computational complexity might be reduced. Next, we provide an illustrative example.

Example 4. Continue to consider system (5.1) in Example 2. Try to find the optimal solution of the optimization problem as follows:

Note that for a given solution, it costs 4 operations to compute its objective value due to the objective function $f(x)$. As a consequence, using the method presented in ^{[31,32,33,34,35,44]}, the optimal solution should be selected from the set of 36 quasi-minimal solutions. This cost

operations. However, using our proposed checking approach before the pair-wise comparison, it cost

operations for obtaining the optimal solution. Obviously, $1.454\times10^{6}$ is much less than $1.488\times10^{42}$. Hence, using our proposed checking approach helps to reduce computational complexity in solving the above problem (5.5).

Replacing the objective function $f(x)$ in problem (5.5), the corresponding computation complexities are as shown in Table 3. The operations of the objective function $f(x)$ are denoted by $O(f(x))$.

5.2.   Application in some decision-making problem

In the existing work ^[7], the FRS with max-product composed inequalities, i.e., system (2.1), was introduced for describing the wireless communication base station system. In such a model, any solution of system (2.1) represents a feasible scheme for arranging the radiation intensity of the electromagnetic wave among the base stations. In order to reduce the radiation intensities of electromagnetic waves, the authors constructed and investigated the following optimization problem:

The constraint system problem (5.6) is exactly our studied system (2.1). Accordingly, any optimal solution of problem (5.6) provides an optimal feasible scheme.

It could be easily verified that there exists a minimal solution $x^{*}$ of system (2.1), such that $x^{*}$ is exactly an optimal solution of problem (5.6). Thereby, the optimal solution of problem (5.6) could be selected from the minimal solution set. As pointed out in Subsection 5.1, our proposed checking approach would be helpful in deriving the minimal solution set. Therefore, our proposed checking approach could also be applied to such an optimization management model in the wireless communication base station system.

5.3.   Demerit of our proposed checking approach and limitation of our studied problem

In the previous subsection, we have shown the merits of our proposed checking approach. However, when the problem size of system (2.1) is small enough and it only has a few quasi-minimal solutions, our proposed checking approach might be no longer superior to the commonly used pair-wise comparison method. This would be the demerit of our proposed checking approach.

As presented above, our proposed approach is just capable of checking whether a given solution is minimal. However, if one aims to find out all the minimal solutions, or the complete solution set, the existing solution-matrix approach ^[7,10] and the FRI path approach in ^[44] would be necessary. Our proposed checking approach serves as a key auxiliary technique in solving system (2.1).

In future research, we will continue to explore the applications of our proposed checking approach for verifying a minimal solution and try to further reduce the computational complexity.

6.   Conclusions

Checking whether a given solution is minimal plays an important role in the studies on the max-product fuzzy relation inequalities. In this work, we proposed an approach for checking the minimality of a given solution. The effectiveness of our proposed approach was demonstrated through a simple example. Moreover, our proposed checking approach is also helpful in deriving the minimal solution set of system (2.1). Our proposed approach and the obtained results were compared to those in the related existing works.

Author contributions

Guocheng Zhu: Investigation, methodology, writing-original draft; Zhining Wang: Methodology, writing-review & editing; Xiaopeng Yang: Conceptualization, funding acquisition, writing-review & editing. All authors have read and approved the final version of the manuscript for publication.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (12271132), Guangdong Basic and Applied Basic Research Foundation (2024A1515010532, 2022A1515011460) and the funds provided by Department of Education of Guangdong Province (2023KQNCX041, XYN202303, 2024ZDZX1027, 2022KSYS003, 2023KTSCX414, 2024KTSCX403, 2021ZDJS044).

Conflict of interest

The authors declare that they have no conflict of interest.