Minimal solutions of fuzzy relation inequalities with addition-min composition 1

Abstract

This paper investigates minimal solutions of fuzzy relation inequalities with addition-min composition. It first shows the conditions that an element is a minimal solution of the inequalities, and presents the conditions that the inequalities have a unique minimal solution. It then proves that every solution of the inequalities has a minimal one and proposes an algorithm to searching for a minimal solution with computational complexity O (n²) where n is the number of unknown variables of the inequalities. This paper finally describes all minimal solutions of the inequalities.

Keywords

Fuzzy relation inequality addition-min composition minimal solution algorithm

1 Introduction

The theory of fuzzy relation inequations with addition-min composition was widely applied to BitTorrent-like Peer-to-Peer file sharing systems since 2012 [4 , 10–12]. Each computer in a BitTorrent-like Peer-to-Peer file sharing systems plays two roles of both client and server, that is to say, every computer in the systems downloads files from the other computers while simultaneously uploads data for them. Suppose that in the systems, there are n users A₁, A₂, …, A_n who are downloading some files. We study the conditions that the ith user A_i receives the file from the other n - 1 users. Assume that the jth user A_j sends the file with quality level x_j to A_i, and the bandwidth between A_i and A_j is a_ij. Limited by the bandwidth, the network traffic that A_i receives from A_j is a_ij ∧ x_j actually. Suppose that the quality requirement of download traffic of A_i must be at least b_i (b_i > 0). Thus the ith user A_i receiving the file from the other n - 1 users should satisfy the following condition: [4, 7]. $\begin{matrix} a_{i 1} \land x_{1} + \dots + a_{i, i - 1} \land x_{i - 1} + a_{i, i + 1} \land x_{i + 1} \\ + \dots + a_{in} \land x_{n} \geq b_{i} . \end{matrix}$ This follows that the condition that the n users in the file sharing systems can successfully download the files can be described as follows: ${\begin{matrix} 0 \land x_{1} + a_{12} \land x_{2} + \dots + a_{1, i - 1} \land x_{i - 1} + a_{1, i} \land x_{i} + \dots + a_{1 n} \land x_{n} \geq b_{1}, \\ a_{21} \land x_{1} + 0 \land x_{2} + \dots + a_{2, i - 1} \land x_{i - 1} + a_{2, i} \land x_{i} + \dots + a_{2 n} \land x_{n} \geq b_{2}, \\ \dots \\ a_{i 1} \land x_{1} + a_{i 2} \land x_{2} + \dots + a_{i, i - 1} \land x_{i - 1} + 0 \land x_{i} + \dots + a_{in} \land x_{n} \geq b_{i}, \\ \dots \\ a_{n 1} \land x_{1} + a_{n 2} \land x_{2} + \dots + a_{n, i - 1} \land x_{i - 1} + a_{n, i} \land x_{i} + \dots + 0 \land x_{n} \geq b_{n} . \end{matrix}$ (1)

Therefore, the mathematical model of formula (1) is a fuzzy relation inequalities as below. ${\begin{matrix} a_{11} \land x_{1} + a_{12} \land x_{2} + \dots + a_{1 n} \land x_{n} \geq b_{1}, \\ a_{21} \land x_{1} + a_{22} \land x_{2} + \dots + a_{2 n} \land x_{n} \geq b_{2}, \\ \dots \\ a_{m 1} \land x_{1} + a_{m 2} \land x_{2} + \dots + a_{mn} \land x_{n} \geq b_{m}, \end{matrix}$ (2) where a_ij, x_j ∈ [0, 1], b_i > 0, and the operator “ + " means the usual addition and a_ij ∧ x_j = min {a_ij, x_j}.

Let J = {1, 2, …, n} and I = {1, 2, …, m}. Then system (2) can be represented as $\sum_{j \in J} a_{ij} \land x_{j} \geq b_{i} for any i \in I .$

A special case of (2) is as follows. $\sum_{j \in J} a_{j} \land x_{j} \geq b .$ (3)

Li and Yang [4] proved that the solution set of system (2) is decided by all minimal solutions, and they provided an algorithm to find a minimal solution of system (2). Since 2012, solving the system (2) and the related optimization problem are interesting for many scholars. For example, Yang [7] defined the pseudominimal indexes of system (2) and he showed an algorithm (called the PMI algorithm) to obtain the set of pseudominimal indexes. Furthermore, by calculating the pseudominimal indexes, he verified that each optimal solution of the optimizations with system (2) as constraints is a minimal one of system (2) and suggested an algorithm to find the optimal solution. Guu and Wu [3] proved that there is an uncountably infinite number of minimal solutions for system (2). Thus from the computational viewpoint, Yang’s algorithm which is based on the PMI algorithm is inefficient. In the meanwhile, Yang et al. [10] also proved that there is an infinite number of minimal solutions if system (2) has more than one minimal solution and provided an algorithm for getting the variable-ordering solutions for system (2) in which a variable-ordering solution is a minimal one. Also, Yang [8] was aware of the existence of an infinite number of minimal solutions and hence he turned to checking the unique conditions of minimal solutions and showed an algorithm for obtaining minimal solutions by applying the critical set of system (2). Especially, Cao et al. [1] presented that each solution of system (2) is between a minimal one and the greatest one by using Zorn’s lemma. Thus the solution set of system (2) is completely described by the greatest solution and their minimal ones (see [1, Theorem 5]). Latterly, Li and Wang [5] pointed out that using both Yang’s algorithm (see [4, p. 455]) and Yang’s PMI algorithm of [7], we cannot obtain a minimal solution of a given one. Moreover, they directly got that for each solution of system (2) there is a minimal solution that is less than or equal to the solution, and they then proposed an algorithm to compute a minimal solution for a given one. The above literatures clearly tell us: on one hand, minimal solutions of system (2) play an important role in solving both system (2) and the optimizations with system (2) as constraints; on the other hand, an algorithm may be inefficient if it can just find a finite number of minimal solutions of system (2) when system (2) has more than one minimal solution. Therefore, how to describe all minimal solutions of system (2) becomes an interesting problem. This article will focuses on finding all minimal solutions of system (3).

The remainder of this article is organized as follows. Sections 2 provides a sufficient and necessary condition that an x is a minimal solution of (3), and presents two sufficient and necessary conditions that the system (3) has a unique minimal solution. Sections 3 shows that every solution of (3) has a minimal one, and gives an algorithm for searching one minimal solution of (3) with computational complexity O (n²). Section 4 describes all minimal solutions of (3). A conclusion is drawn in Section 5.

2 Characterizations of minimal solutions

In this section, we shall present a sufficient and necessary condition that an x is a minimal solution of (3) and show two sufficient and necessary conditions that the system (3) has a unique minimal solution.

Let $x^{1} = (x_{1}^{1}, x_{2}^{1}, \dots, x_{n}^{1}), x^{2} = (x_{1}^{2}, x_{2}^{2}, \dots, x_{n}^{2}) \in [0, 1]^{n}$ . Then we say x¹ ≤ x² if and only if $x_{j}^{1} \leq x_{j}^{2}$ for all j ∈ J, and x¹ < x² if and only if x¹ ≤ x² and there exists a j ∈ J such that $x_{j}^{1} < x_{j}^{2}$ . Denoted by X (A, b) = {x ∈ [0, 1] ⁿ ∣ ∑_j∈Ja_j ∧ x_j ≥ b} the solution set of (3). We first need the following definition and lemma.

Definition 2.1. [4]An $\hat{x} \in X (A, b)$ is called the greatest solution if $x \leq \hat{x}$ for all x ∈ X (A, b). An $\overset{ˇ}{x} \in X (A, b)$ is called a minimal solution if $x \leq \overset{ˇ}{x}$ for all x ∈ X (A, b) implies $x = \overset{ˇ}{x}$ . Denote the set of all minimal solutions of (3) by $\overset{ˇ}{X} (A, b)$ .

Lemma 2.1. [6]X (A, b)≠ ∅ if and only if ∑_j∈Ja_j ≥ b.

Then it’s clear that the following two propositions hold.

Proposition 2.1. If there exists a j ∈ J such that a_j ≥ b, then (3) is solvable.

Proposition 2.2. If x = (x₁, x₂, …, x_n) ∈ X (A, b), then ∑_j∈Jx_j ≥ b.

In what follows, we shall give a sufficient and necessary condition that $x = (x_{1}, x_{2}, \dots, x_{n}) \in \overset{ˇ}{X} (A, b)$ . We first have the following two propositions.

Proposition 2.3. If $x = (x_{1}, x_{2}, \dots, x_{n}) \in \overset{ˇ}{X} (A, b)$ , then x_j ≤ a_j for any j ∈ J.

Proof. Note that ∑_j∈Ja_j ∧ x_j ≥ b since $x \in \overset{ˇ}{X} (A, b)$ . Assume that J₀ = {j∈ J ∣ x_j > a_j} ≠ ∅. Then

$\begin{matrix} \sum_{j \in J} a_{j} \land x_{j} & = & \sum_{j \in J_{0}} a_{j} \land x_{j} + \sum_{j \in J ∖ J_{0}} a_{j} \land x_{j} \\ = & \sum_{j \in J_{0}} a_{j} + \sum_{j \in J ∖ J_{0}} x_{j} \\ = & \sum_{j \in J_{0}} a_{j} \land a_{j} + \sum_{j \in J ∖ J_{0}} a_{j} \land x_{j} \\ \geq & b . \end{matrix}$ (4) Suppose j₀ ∈ J₀ and let $x^{*} = (x_{1}^{*}, x_{2}^{*}, \dots, x_{n}^{*})$ be defined as $x_{j}^{*} = {\begin{matrix} a_{j}, j = j_{0}, \\ x_{j}, j \neq j_{0} . \end{matrix}$ Then from (4), x^* ∈ X (A, b) and x^* < x, contrary to $x \in \overset{ˇ}{X} (A, b)$ . Therefore, J₀ =∅, i.e. x_j ≤ a_j for any j ∈ J.□ Proposition 2.4. Let x = (x₁, x₂, …, x_n) ∈ X (A, b). Then $x \in \overset{ˇ}{X} (A, b)$ if and only if ∑_j∈Jx_j = b.

Proof. Let x = (x₁, x₂, …, x_n) ∈ X (A, b). Suppose that there is an $x_{*} = (x_{* 1}, x_{* 2}, \dots, x_{* n}) \in X (A, b)$ such that x_* ≤ x. Then b ≤ ∑_j∈Jx_*j ≤ ∑_j∈Jx_j = b by Proposition 2.2, so ∑_j∈Jx_*j = ∑_j∈Jx_j. This follows that x_* = x. Therefore, by Definition 2.1, $x \in \overset{ˇ}{X} (A, b)$ .

Conversely, suppose ∑_j∈Jx_j > b. Then let $x^{*} = (x_{1}^{*}, x_{2}^{*}, \dots, x_{n}^{*})$ satisfy that $x_{j}^{*} \leq x_{j}$ for any j ∈ J and $\sum_{j \in J} x_{j}^{*} = b$ . Obviously, x^* < x. Thus, by Proposition 2.3, $x_{j}^{*} \leq x_{j} \leq a_{j}$ for any j ∈ J. Hence, $\sum_{j \in J} a_{j} \land x_{j}^{*} = \sum_{j \in J} x_{j}^{*} = b$ , i.e. x^* ∈ X (A, b), contrary to $x \in \overset{ˇ}{X} (A, b)$ . Therefore, ∑_j∈Jx_j = b by Proposition 2.2.□ Propositions 2.3 and 2.4 implies the following theorem.

Theorem 2.1. Let x = (x₁, x₂, …, x_n). Then $x \in \overset{ˇ}{X} (A, b)$ if and only if ∑_j∈Jx_j = b and x_j ≤ a_j for any j ∈ J.

In the following we shall consider the conditions that $\overset{ˇ}{X} (A, b)$ has only one element. We first need the following lemma which is cited from [4].

Lemma 2.2. Let x = (x₁, x₂, …, x_n) ∈ X (A, b). Then

x > 0;

x_j ≥ b - ∑_i∈J\{j}a_i for any j ∈ J;

a_j ≥ b - ∑_i∈J\{j}x_i for any j ∈ J.

Remark 2.1. Denote $max {0, b - \sum_{i \in J \ {j}} a_{i}} = {\dot{a}}_{j}$ and $\dot{a}$ = $({\dot{a}}_{1}, {\dot{a}}_{2}, \dots, {\dot{a}}_{n})$ . Then it follows from Lemma 2.2 that if x = (x₁, x₂, …, x_n) ∈ X (A, b) then it’s clear that $x_{j} \geq {\dot{a}}_{j}$ for any j ∈ J.

Then we have the following three propositions.

Proposition 2.5. If $x = (x_{1}, x_{2}, \dots, x_{n}) \in \overset{ˇ}{X} (A, b)$ , then ${\dot{a}}_{j} \leq x_{j} \leq \min {b, a_{j}}$ for any j ∈ J.

Proof. Theorem 2.1 means that ∑_j∈Jx_j = b and x_j ≤ a_j for any j ∈ J since $x \in \overset{ˇ}{X} (A, b)$ , i.e., x_j ≤ min {b, a_j} for any j ∈ J, which together with Remark 2.1 implies that $\dot{a_{j}} \leq x_{j} \leq \min {b, a_{j}}$ .□

Remark 2.2. If a, b ∈ [0, 1], then a ∧ x ≥ b is solvable if and only if a ≥ b. Furthermore, x = b is the unique minimal solution when a ∧ x ≥ b is solvable.

Proposition 2.6. Let $x = (x_{1}, x_{2}, \dots, x_{n}) \in \overset{ˇ}{X} (A, b)$ . If ∑_j∈Ja_j = b, then x_j = a_j for any j ∈ J.

Proof. By Theorem 2.1, we have x_j ≤ a_j for any j ∈ J since $x \in \overset{ˇ}{X} (A, b)$ . If there exists j₀ ∈ J such that x_{j
₀} < a_{j
₀}, then ∑_j∈Jx_j < ∑_j∈Ja_j = b, which is in conflict with Proposition 2.4.□

Proposition 2.7. If ∑_j∈Ja_j > b and | {j ∈ J ∣ a_j > 0} |>1, then (3) has more than one minimal solution.

Proof. Let x = (x₁, x₂, …, x_n) be such that ∑_j∈Jx_j = b and x_j ≤ a_j for any j ∈ J. Then by Theorem 2.1, $x \in \overset{ˇ}{X} (A, b)$ . Denote J_x = {j ∈ J ∣ x_j > 0}. There are two cases as follows. Case (1). If |J_x|=1, then without loss of generality, suppose J_x = {i}. Hence, by hypothesis, there exists j ∈ J such that a_j > 0 and j ≠ i. Let x_* = (x_*1, x_*2, …, x_*n) satisfy that 0 < x_*i < x_i, x_*i + x_*j = x_i and x_*j ≤ a_j with ∑_j∈Jx_*j = b. Thus it follows from Theorem 2.1 that $x_{*} \in \overset{ˇ}{X} (A, b)$ and x ≠ x_*. Case (2). If |J_x|>1 and i ∈ J_x, then by hypothesis, there exists x_** = (x_**1, x_**2, …, x_**n) which satisfies 0 < x_**i < x_i, x_**i + x_**j = x_i + x_j and x_**j ≤ a_j with ∑_j∈Jx_**j = b. Again, by Theorem 2.1, $x_{* *} \in \overset{ˇ}{X} (A, b)$ and x ≠ x_**.□

Let J_* = {j ∈ J ∣ a_j > 0}. Then we get the theorem as follows.

Theorem 2.2. If X (A, b)≠ ∅, then (3) has a unique minimal solution if and only if one of the following two conditions holds.

(1) |J_*|>1 and ∑_j∈Ja_j = b;

(2) |J_*|=1.

Proof. Suppose that (3) has the unique minimal solution x = (x₁, x₂, …, x_n). If |J_*|=1, then (2) is true. If |J_*|>1, then, due to Lemma 2.1 and Proposition 2.7, ∑_j∈Ja_j = b. Therefore, (1) holds.

The converse implication, if (1) is true, then let x = (x₁, x₂, …, x_n) satisfy x_j = a_j for any j ∈ J. Thus by Theorem 2.1, $x \in \overset{ˇ}{X} (A, b)$ . Further, by Proposition 2.6, x is the unique minimal solution of (3). If (2) is true, then by Remark 2.2, (3) has a unique minimal solution.□ With Theorem 2.2, the following corollary holds.

Corollary 2.1. [6]If ∑_j∈Ja_j = b, then x = (a₁, a₂, …, a_n) is the unique minimal solution of (3).

Theorem 2.2 and Remark 2.1 imply the following theorem which is a special case of Theorem 4 in [7].

Theorem 2.3. (3) has a unique minimal solution if and only if $\dot{a} \in X (A, b)$ .

Remark 2.3. With Remark 2.1, if (3) has a unique minimal solution, then $\dot{a}$ is the unique minimal solution.

3 An algorithm for finding a minimal solution

In this section, we shall prove that every solution of (3) has a minimal one. Then we shall describe the set of solutions of (3) and give an algorithm for finding a minimal solution of (3).

Notice that if ∑_j∈Ja_j = b, then by Corollary 2.1, (3) has the unique minimal solution x = (a₁, a₂, …, a_n). Hence, in what follows, we just consider ∑_j∈Ja_j > b.

Proposition 3.1. If there exists an l ∈ J such that $b - \sum_{j = l}^{n} a_{j} \leq 0$ and $b - \sum_{j = l + 1}^{n} a_{j} > 0$ , then $x = (0, 0, \dots, 0, b - \sum_{j = l + 1}^{n} a_{j}, a_{l + 1}, \dots, a_{n})$ is a minimal solution of (3).

Proof. We first prove $a_{l} \geq b - \sum_{j = l + 1}^{n} a_{j}$ . In fact, if $a_{l} < b - \sum_{j = l + 1}^{n} a_{j},$ then $b - \sum_{j = l}^{n} a_{j} > 0$ , contrary to $b - \sum_{j = l}^{n} a_{j} \leq 0$ .

Therefore, we have ∑_j∈Ja_j ∧ x_j= $a_{l} \land (b - \sum_{j = l + 1}^{n} a_{j}) + a_{l + 1} + \dots + a_{n}$ = $(b - \sum_{j = l + 1}^{n} a_{j}) + a_{l + 1} + \dots + a_{n}$ =b, i.e., x ∈ X (A, b). Finally, by Proposition 2.4, $x \in \overset{ˇ}{X} (A, b)$ .□

Theorem 3.1. If x ∈ X (A, b), then there exists an $x_{*} \in \overset{ˇ}{X} (A, b)$ such that x_* ≤ x.

Proof. Let x = (x₁, x₂, …, x_n) ∈ X (A, b). Then by Proposition 2.2, ∑_j∈Jx_j ≥ b. We distinguish two cases.

Case (1). If ∑_j∈Jx_j = b, then using Proposition 2.4, $x \in \overset{ˇ}{X} (A, b)$ . Let x_* = x. Then x_* ≤ x.

Case (2). If ∑_j∈Jx_j > b, and there exists a j₀ ∈ J such that x_{j
₀} > a_{j
₀}, then let u = (u₁, …, u_n) = (x₁, …, x_j₀-1, a_{j
₀}, x_j₀+1, …, x_n). Clearly, u ∈ X (A, b). Therefore, in the following, we always suppose x = (x₁, x₂, …, x_n) satisfy both ∑_j∈Jx_j > b and x_j ≤ a_j for any j ∈ J. Let x_{j
₀} be the first component of (x₁, x₂, …, x_n) which satisfies x_{j
₀} ≠ 0. If $\sum_{j = j_{0} + 1}^{n} x_{j} \leq b$ , then set $y = (0, \dots, 0, \overset{j_{0}}{\overset{↑}{x_{j_{0}} - d_{j_{0}}}}, x_{j_{0} + 1}, \dots, x_{n})$ in which $d_{i} = \sum_{j = i}^{n} x_{j} - b$ for any i ∈ J. Moreover, applying Theorem 2.1, we have $y \in \overset{ˇ}{X} (A, b)$ and y ≤ x. Otherwise, $\sum_{j = j_{0} + 1}^{n} x_{j} > b$ . Then put x⁽¹⁾ = (0, …, 0, x_j₀+1, …, x_n). Obviously, x⁽¹⁾ ∈ X (A, b). Let x_{l
₀} be the first component of (0, …, 0, x_j₀+1, …, x_n) which satisfies x_{l
₀} ≠ 0. If $\sum_{j = l_{0} + 1}^{n} x_{j} \leq b$ , then set $z = (0, \dots, 0, \overset{l_{0}}{\overset{↑}{x_{l_{0}} - d_{l_{0}}}}, x_{l_{0} + 1}, \dots, x_{n})$ . Again, by Theorem 2.1, we have $z \in \overset{ˇ}{X} (A, b)$ and z ≤ x. Otherwise, $\sum_{j = l_{0} + 1}^{n} x_{j} > b$ . Then put x⁽²⁾ = (0, …, 0, x_l₀+1, …, x_n). Obviously, x⁽²⁾ ∈ X (A, b). Continuing as above, we must come to one of the following two subcases since J is finite. (i) There is a k such that $x^{(k)} = (0, \dots, 0, \overset{h}{{\overset{↑}{x}}_{h}}, \dots, x_{n})$ with x_h ≠ 0 and $\sum_{j = h + 1}^{n} x_{j} \leq b$ . In this subcase, set $x_{*} = (0, \dots, 0, \overset{h}{\overset{↑}{x_{h} - d_{h}}}, x_{h + 1}, \dots, x_{n})$ . Then by Theorem 2.1, $x_{*} \in \overset{ˇ}{X} (A, b)$ and x_* ≤ x. (ii) x_n > b. In this subcase, set $x_{*} = (0, \dots, 0, \overset{n}{\overset{↑}{b}})$ . Using Theorem 2.1, $x_{*} \in \overset{ˇ}{X} (A, b)$ and x_* ≤ x.□ Notice that the proof of Theorem 3.1 is essentially different from that of Theorem 3.1 in [5] although one is a special case of the other one.

Lemma 3.1. [4, 7]If (3) is solvable, then (1, 1, …, 1) is the greatest solution.

From Lemma 3.1 and Theorem 3.1, we deduce the following theorem.

Theorem 3.2. [4] $X (A, b) = ⋃_{\overset{ˇ}{x} \in \overset{ˇ}{X} (A, b)} {x \in X ∣ \overset{ˇ}{x} \leq x \leq (1, 1, \dots, 1)}$ .

From the proof of Theorem 3.1, we can suggest an algorithm to search for a minimal solution of (3) when ∑_j∈Ja_j > b.

Algorithm 3.1. Input: x : = (a₁, a₂, …, a_n). Output: x.

Step 1: i : =1.

Step 2: Compute $d_{i} = \sum_{j = i}^{n} x_{j} - b$ .

Step 3: If d_inotgreaterthan0, then go to step 6.

Step 4: If i < n, then i : = i + 1, go to step 2.

Step 5: $x : = (0, \dots, 0, \overset{n}{\overset{↑}{b}})$ , go to step 7.

Step 6: $x : = (0, \dots, 0, \overset{i - 1}{\overset{↑}{a_{i - 1} - d_{i - 1}}}, a_{i}, \dots, a_{n})$ .

Step 7: End.

Notable that one can verify that the computational complexity of Algorithm 3.1 is O (n²).

The following two examples will illustrate Algorithm 3.1.

Example 3.1. Consider a minimal solution of the following inequality. $0.8 \land x_{1} + 0.9 \land x_{2} + 0.6 \land x_{3} \geq 1.4 .$

Input: x : = (0.8, 0.9, 0.6).

Output: x.

Step 1: i : =1.

Step 2: Compute $d_{1} = \sum_{j = 1}^{3} a_{j} - b = 0.9$ .

Step 3: d₁ > 0.

Step 4: i = 1 ≠3, i : = i + 1 =2.

Step 5: Compute $d_{2} = \sum_{j = 2}^{3} a_{j} - b = 0.1$ .

Step 6: d₂ = 0.1 > 0.

Step 7: i = 2 ≠3, i : = i + 1 =3.

Step 8: Compute d₃ = a₃ - b = -0.8.

Step 9: d₃ ≯ 0.

Step 10: x : = (0, a₂ - d₂, a₃) = (0, 0.8, 0.6).

Step 11: End.

Example 3.2. Consider a minimal solution of the following inequality. $0.8 \land x_{1} + 0.9 \land x_{2} + 1.5 \land x_{3} \geq 1.4 .$

Input: x : = (0.8, 0.9, 1.5).

Output: x.

Step 1: i : =1.

Step 2: Compute $d_{1} = \sum_{j = 1}^{3} a_{j} - b = 1.8$ .

Step 3: d₁ > 0.

Step 4: i = 1 ≠3, i : = i + 1 =2.

Step 5: Compute $d_{2} = \sum_{j = 2}^{3} a_{j} - b = 1$ .

Step 6: d₂ > 0.

Step 7: i = 2 ≠3, i : = i + 1 =3.

Step 8: Compute d₃ = a₃ - b = 0.1.

Step 9: d₃ > 0.

Step 10: i = 3.

Step 11: x : = (0, 0, b) = (0, 0, 1.4).

Step 12: End.

4 The set of minimal solutions

In this section, we shall describe the set of minimal solutions of (3).

Theorem 4.1. Let x = (x₁, x₂, …, x_n). Then $\overset{ˇ}{X} (A, b) = {X | \begin{matrix} \max {0, b - \sum_{j = 2}^{n} a_{j}} \leq x_{1} \leq \min {b, a_{1}}; \\ \max {0, b - \sum_{k = 1}^{j - 1} x_{k} - \sum_{k = j + 1}^{n} a_{k}} \leq x_{j} \leq \min {b - \sum_{k = 1}^{j - 1} x_{k}, a_{j}}, j = 2, \dots, n - 1; \\ x_{n} = b - \sum_{j = 1}^{n - 1} x_{j} \end{matrix}} .$

Proof. The first part, for convenience, let $a_{1}^{*} = \max {0, b - \sum_{j = 2}^{n} a_{j}}$ and $a_{j}^{*} = \max {0, b - \sum_{k = 1}^{j - 1} x_{k} - \sum_{k = j + 1}^{n} a_{k}}$ where j = 2, …, n - 1. Then $\begin{matrix} \sum_{j \in J} a_{j} \land x_{j} \\ \geq & \sum_{j = 1}^{n - 1} a_{j} \land a_{j}^{*} + a_{n} \land x_{n} \\ \geq & a_{1} \land (b - \sum_{j = 2}^{n} a_{j}) + a_{2} \land (b - x_{1} - \sum_{j = 3}^{n} a_{j}) \\ + \dots + a_{n - 1} \land (b - \sum_{j = 1}^{n - 2} x_{j} - a_{n}) \\ + a_{n} \land (b - \sum_{j = 1}^{n - 1} x_{j}) \\ = & (b - \sum_{j = 2}^{n} a_{j}) + a_{2} \land a_{2} + \dots + a_{n - 1} \land a_{n - 1} \\ + a_{n} \land (b - (b - \sum_{j = 2}^{n} a_{j} + a_{2} + \dots + a_{n - 1})) \\ = & b - \sum_{j = 2}^{n} a_{j} + a_{2} + a_{3} + \dots + a_{n} \\ = & b, \end{matrix}$ which yields x ∈ X (A, b). Furthermore, $x_{n} = b - \sum_{j = 1}^{n - 1} x_{j}$ , i.e., ∑_j∈Jx_j = b. With Proposition 2.4, $x \in \overset{ˇ}{X} (A, b)$ .

Conversely, let $x \in \overset{ˇ}{X} (A, b)$ . Then from Proposition 2.5, $\max {0, b - \sum_{j = 2}^{n} a_{j}} \leq x_{1} \leq \min {b, a_{1}}$ . After x₁ is fixed, (3) is transformed into the following inequality: $a_{2} \land x_{2} + \dots + a_{n} \land x_{n} \geq b - x_{1} .$ (5) Thus by Proposition 2.4, (x₂, x₃, …, x_n) is a minimal solution of (5) since $\sum_{j = 2}^{n} x_{j} = b - x_{1}$ and (x₂, x₃, …, x_n) is a solution of (5). Again, by Proposition 2.5, $\max {0, b - x_{1} - \sum_{j = 3}^{n} a_{j}} \leq x_{2} \leq \min {b - x_{1}, a_{2}}$ . Continuing as above, we in turn have $\max {0, b - \sum_{j = 1}^{n - 2} x_{j} - a_{n}} \leq x_{n - 1} \leq \min {b - \sum_{j = 1}^{n - 2} x_{j}, a_{n - 1}}$ and $x_{n} = b - \sum_{j = 1}^{n - 1} x_{j}$ .□

By Remark 2.1, it is clear that $a_{1}^{*} = \dot{a_{1}}$ .

Theorem 4.2. Let x = (x₁, x₂, …, x_n). Then $\overset{ˇ}{X} (A, b) = {X | \begin{matrix} \dot{a_{j}} = \max {0, b - \sum_{i \in J \ {j}} a_{i}} \leq x_{j} \leq \min {b, a_{j}}, j = 1, 2, \dots, n, \\ \sum_{j \in J} x_{j} = b \end{matrix}} .$

Proof. If $x \in \overset{ˇ}{X} (A, b)$ , then from Propositions 2.4 and 2.5, $\dot{a_{j}} \leq x_{j} \leq \min {b, a_{j}}$ for any j ∈ J and ∑_j∈Jx_j = b.

In the converse implication, because $\dot{a_{j}} \leq x_{j} \leq \min {b, a_{j}}$ for any j ∈ J, we have x_j ≤ a_j for any j ∈ J. Therefore, by Theorem 2.1, $x \in \overset{ˇ}{X} (A, b)$ since ∑_j∈Jx_j = b.□

Example 4.1. Consider all minimal solutions of the following inequality $0.8 \land x_{1} + 0.6 \land x_{2} + 0.2 \land x_{3} \geq 1.5 .$

Applying Theorem 4.2, it is evident that $\overset{ˇ}{X} (A, b) = {x = (x_{1}, x_{2}, x_{3}) ∣ 0.7 \leq x_{1} \leq 0.8, 0.5 \leq x_{2} \leq 0.6, 0.1 \leq x_{3} \leq 0.2 and \sum_{j \in J} x_{j} = 1.5}$ .

5 Conclusions

We obtained some characterizations of minimal solutions of (3), and showed that every solution of (3) has a minimal one. Then we provided an algorithm for searching for a minimal solution with computational complexity O (n²) and described all minimal solutions of (3). In the future, we shall apply our above results to investigate minimal solutions of (2).

Footnotes

Acknowledgments

The authors are grateful to the responsible editor and the anonymous referees for their valuable comments and suggestions, which helps the authors to improve the earlier version of this paper.

References

Cao

B.Y.

, Yang

X.P.

and Zhou

X.G.

Properties of fuzzy relation inequalities with addition-min composition, Fuzzy Information and Engineering and Decision (B. Y. Cao Ed.), Advances in Intelligent Systems and Computing, Springer 646 (2018), 177–185.

Guo

F.F.

and Shen

A smoothing approach for minimizing a linear function subject to fuzzy relation inequalities with addition-min composition, Int J Fuzzy Syst 21 (2019), 281–290.

Guu

S.M.

and Wu

Y.K.

A linear programming approach for minimizing a linear function subject to fuzzy relational inequalities with addition-min composition, IEEE Transactions on Fuzzy Systems 25 (2017), 985–992.

J.X.

and Yang

S.J.

Fuzzy relation inequalities about the data transmission mechanism in BitTorrent-like Peer-to-Peer file sharing systems, in: Proceedings of the 2012 9th International Conference on Fuzzy systems and Knowledge Discover, IEEE: FSKD (2012), 452–456.

and Wang

X.-p.

Remarks on minimal solutions of fuzzy relation inequalities with addition-min composition, Fuzzy Sets and Systems 410 (2021), 19–26.

X.B.

and Sun

Solution sets of fuzzy relation equations with addition-min composition, Journal of Leshan Normal University 32 (2017), 6–10 (in Chinese).

Yang

S.J.

An algorithm for minizing a linear objective function subject to the fuzzy relation inequalities with addition-min composition, Fuzzy Sets and Systems 255 (2014), 41–51.

Yang

S.J.

Some results of fuzzy relation inequalities with addition-min composition, IEEE Transactions on Fuzzy Systems 26 (2018), 239–245.

Yang

X.P.

Optimal-vector-based algorithm for solving min-max programming subject to addition-min fuzzy relation inequality, IEEE Transactions on Fuzzy Systems 25 (2017), 1127–1140.

10.

Yang

X.P.

, Lin

H.T.

, Zhou

X.G.

and Cao

B.Y.

Addition-min fuzzy relation inequalities with application in Bit Torrent-like Peer-to-Peer file sharing system, Fuzzy Sets and Systems 343 (2018), 126–140.

11.

Yang

X.P.

, Zhou

X.G.

and Cao

B.Y.

Multi-level linear programming subject to addition-min fuzzy relation inequalities with application in Peer-to-Peer file sharing system, Journal of Intelligent & Fuzzy Systems 28 (2015), 2679–2689.

12.

Yang

X.P.

, Zhou

X.G.

and Cao

B.Y.

Min-max programming problem subject to addition-min fuzzy relation inequalities, IEEE Transactions on Fuzzy Systems 24 (2016), 111–119.