Unbalanced signed graphs with eigenvalue properties

1.   Introduction

In recent years, the addition-min fuzzy relation inequality (FRI) was first introduced in ^[1,2] for describing the flow constraints in the peer-to-peer (P2P) network system. Since the minimal solutions play a key role in constructing the complete solution set for the addition-min FRIs ^[3,4,5], Li et al. ^[1] proposed a feasible approach to find some specific minimal solutions. However, as shown in ^[2], the addition-min FRIs usually have an infinite number of minimal solutions, and it is difficult to determine all the minimal solutions. To obtain specific minimal solutions, various approaches have been developed. In ^[6], the lexicographic minimum solution was defined and studied. An effective resolution algorithm and some illustrative numerical examples were provided. The concept of the lexicographic minimum solution was also extended to random-term-absent addition-min FRIs ^[7]. It can be formally proven that any lexicography minimum solution should also be a minimal solution in the addition-min FRI system. In ^[8], Li et al. investigated another kind of minimal solution for addition-min FRIs. The authors attempted to find a minimal solution that was less than or equal to a given solution ^[8]. Moreover, to obtain specific minimal solutions, solving an optimization problem is also an effective approach. For instance, the optimization problem with a linear objective function was studied in ^[9,10], with addition-min FRIs constraints. Considering the fairness among the terminals in the P2P network system, Yang et al. ^[11] and Chiu et al. ^[12] further investigated fuzzy relation minimax programming with addition-min composition. However, it was shown that its optimal solutions were usually nonunique. Thus, Wu et al. ^[13] and Yang et al. ^[14] further searched for the minimal optimal solutions. By adding some weighted factors to the terminals, the corresponding fuzzy relation weighted minimax programming was also investigated ^[15,16,17].

In references ^{[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17]}, addition-min FRIs were introduced to investigate the P2P network system. As noted in ^{[18,19,20,21]}, by applying the addition-min FRIs to model the P2P network system, the authors considered the total download speed of each terminal and downloaded its requested data from other terminals. However, it was also indicated in ^{[18,19,20,21]} that, in some cases, the highest download speed should be considered. Next, we describe the requirements of the highest download speed for the terminals in a P2P network system. Similarly, it is assumed that there are $n$ terminals in the system, represented by $T_{1}, T_{2}, \cdots, T_{n}$ (see Figure 1). After accepting the downloading request from other terminals, we suppose that terminal $T_{j}$ transmits its local file to any other terminal at quality level $t_{j}$. If the bandwidth between $T_{i}$ and $T_{j}$ (exactly from $T_{j}$ to $T_{i}$) is $a_{ij}$ (see Figure 2), then the actual download traffic of $T_{i}$ from $T_{j}$ is $a_{ij}\wedge t_{j}$.

Considering the total download traffic of each terminal, the P2P network system can be modeled by the addition-min FRIs. However, in some cases, the specific file should be downloaded from a single terminal. In such cases, $T_{i}$ downloads its requested file from the terminal with the highest download traffic, i.e., $a_{i1}\wedge t_{1} \vee a_{i2}\wedge t_{2} \vee\cdots\vee a_{in}\wedge t_{n}$. Let us suppose that the requirement of the highest download traffic of $T_{i}$ is no less than $b_{i}$, $i = 1, 2, \cdots, m$. Then the requirements of all the terminals in a P2P network system should be modeled by the following max-min FRIs:

Moreover, if the requirement of each terminal for the highest download speed has both an upper bound and a lower bound, then the corresponding max-min FRIs should be further written as

For inconsistent system (1.1), Yang established an evaluation model for a given vector, based on which the approximate solution was defined and investigated ^[22]. For the consistent system (1.1), Zhong et al. ^[23] focused on the lexicographic minimum solution. Xiao et al. investigated the evaluation and derived a classification of system solutions (1.1) ^[24]. A resolution algorithm was developed with an illustrative example. Moreover, the lexicographic minimum solution was also introduced for the above system (1.2) ^[25]. Then considering the stability of the P2P network system, Chen et al. ^[26] defined the concept of interval solutions for system (1.2). The authors proposed an effective algorithm to find the so-called widest interval solution of system (1.2) in ^[26].

As mentioned above, with the constraint system of addition-min FRIs, weighted minimax programming, or even minimax programming as its specific form, has been studied, providing some efficient resolution algorithms ^{[11,12,13,14,15,16,17]}. However, when considering the highest download speed, the relevant weighted minimax programming has not been studied for the corresponding max-min system (1.2). Consequently, we focus on such an optimization problem in this work. The formulistic form of the weighted minimax programming subject to system (1.2) is

As shown in ^{[11,12,13,14,15,16,17]}, in system (1.2) or problem (1.3), $t_{j}$ (measure: Mbps) represents the quality level on which the $j$th terminal shares (sends out) its local resources with the other terminals. To decrease network congestion, system managers usually try to minimize the values of $t_{1}, t_{2}, \cdots, t_{n}$. However, in most cases, these values cannot be minimized simultaneously. Instead of minimizing all these variables, minimizing a specific function with the variables $t_{1}, t_{2}, \cdots, t_{n}$ is much more realistic. For instance, in problem (1.3), we adopt the weighted minimax function. In such a weighted minimax function in (1.3), the parameter $c_{j}$ represents the weighted factor of the $j$th terminal in the P2P network system. In this work, we design several effective algorithms for identifying the optimal solution.

In summary, the innovations and contributions of this work can be summarized as follows:

(ⅰ) Instead of the total download traffic of the terminal, we consider the highest download traffic. Consequently, the corresponding max-min FRIs are employed.

(ⅱ) To decrease network congestion in the P2P network system, we consider a given weighted factor for each terminal. Moreover, we further establish a relevant weighted minimax programming problem with max-min FRI constraints.

(ⅲ) To solve our established weighted minimax optimization model, we propose the so-called single-constraint programming approach for identifying the optimal solution.

The following content is organized as follows. In Section 2, we describe some foundational concepts and results on max-min FRIs, i.e., system (1.2). Our major results are presented in Section 3. In this section, we introduce the single-constraint programming (SCP) approach for addressing our studied problem (1.3). The original problem (1.3) is separated into several subproblems and solved. Moreover, our proposed approach is a step-by-step SCP-based algorithm. In Section 4, a detailed numerical example is provided to demonstrate the SCP-based algorithm. In Section 5, we compare our problem and the proposed method to the existing ones. Section 6 provides a simple conclusion.

2.   On the max-min fuzzy relation inequalities

In this section, we provide some foundational results on the max-min fuzzy relation inequalities, i.e., system (1.2). These existing results are helpful for the resolution of problem (1.3).

Let us denote

Then we represent system (1.2) as

Moreover, the solution set of system (1.2) is indeed

For convenience, we let

Definition 1 (Consistent; Maximum solution ^[25]) System (1.2) is said to be consistent when its solution set is nonempty, i.e., $\mathcal{T}^{A, b, d}\neq\emptyset$; otherwise, system (1.2) is inconsistent. When system (1.2) is consistent and there exists a solution $\overline{t}\in\mathcal{T}^{A, b, d}$ such that $\overline{t}\geq t$ for any $t\in\mathcal{T}^{A, b, d}$, then we say $\overline{t}$ is the maximum solution of (1.2).

In system (1.2), we construct the vector $\hat{t} = (\hat{t}_{1}, \hat{t}_{2}, \cdots, \hat{t}_{n})$ as follows:

where $\mathcal{I}_{j} = \{i\in \mathcal{I}|a_{ij} > d_{i}\}$, $\forall j\in \mathcal{J}$. The vector $\hat{t}$ is important to determine whether system (1.2) is consistent.

Proposition 1. ^[25] Let $t\in \mathcal{T}^{A, b, d}$ be a solution of system (1.2), and the vector $\hat{t}$ is defined by (2.2). Then, we have $t\leq\hat{t}$.

Theorem 1. ^[25] System (1.2) is consistent, i.e., $\mathcal{T}^{A, b, d}\neq\emptyset$, if and only if $\hat{t}\in \mathcal{T}^{A, b, d}$.

According to Proposition 1 and Theorem 1, we know that when $\mathcal{T}^{A, b, d}\neq\emptyset$, $\hat{t}$ should be the unique maximum solution of system (1.2). The potential maximum solution $\hat{t}$ can be used to check the consistency of (1.2).

Definition 2. (Minimal solution ^[25]) Let (1.2) be consistent and $\check{t}\in\mathcal{T}^{A, b, d}$. We say that $\check{t}$ is a minimal solution if there is no $t\in\mathcal{T}^{A, b, d}$ such that $t\leq\check{t}$ and $t\neq\check{t}$.

The conservative path approach was proposed in ^[27,28] to obtain all the minimal solutions of the system (1.2). Moreover, it was shown that system (1.2) has a finite number of minimal solutions when it is consistent. For system (1.2), we denote the set of all minimal solutions by

Based on the maximum solution $\hat{t}$ and the minimal solution set $\check{\mathcal{T}}^{A, b, d}$, the complete solution set to (1.2) can be characterized by Theorem 2.

Theorem 2. ^[25] When system (1.2) is consistent, the solution set $\mathcal{T}^{A, b, d}$ is

Since all minimal solutions can be found by the conservative path approach ^[27,28], one can obtain the complete solution set $\mathcal{T}^{A, b, d}$ for system (1.2).

3.   Resolution of problem (1.3)

3.1.   Existence of the optimal solution and the SCP-based approach to solve problem (1.3)

In this subsection, we first illustrate the existence of the optimal solution for problem (1.3). The optimal solution exists if and only if the feasible domain, i.e., $\mathcal{T}^{A, b, d}$, is nonempty. Afterward, we assume $\mathcal{T}^{A, b, d}\neq\emptyset$, and we attempt to solve problem (1.3). The original problem (1.3) is separated into $m$ subproblems according to the constraints, i.e., system (1.2). Each subproblem has the same objective function as problem (1.3) and a single inequality in the constraint. Thus, each subproblem is indeed a single-constraint programming (SCP) problem. The optimal solution of problem (1.3) can be generated by the optimal solutions of the subproblems. Since problem (1.3) is solved via single-constraint programming, we refer to our resolution method as the SCP-based approach.

Theorem 3. (Existence of the optimal solution) System (1.2) is consistent, i.e., $\mathcal{T}^{A, b, d}\neq\emptyset$, if and only if problem (1.3) has at least one optimal solution.

Proof. It has been shown previously that system (1.2) has a finite number of minimal solutions since it is consistent. Without loss of generality, we denote the minimal solution set by

The objective function values of $\{\check{t}^{1}, \check{t}^{2}, \cdots, \check{t}^{s}\}$ can be found as $\{z(\check{t}^{1}), z(\check{t}^{2}), \cdots, z(\check{t}^{s})\}$. Let us denote

Moreover, there exists $l^{*}\in \{1, 2, \cdots, s\}$ such that $z(\check{t}^{l^{*}}) = z^{*}$, and

Obviously, the minimal solution $\check{t}^{l^{*}}$ is also a feasible solution to problem (1.3). Next, we further verified that it is an optimal solution.

Let $t\in \mathcal{T}^{A, b, d}$ be an arbitrary solution of (1.2). According to Theorem 2, $l'\in \{1, 2, \cdots, s\}$ and $\check{t}^{l'}\in \check{\mathcal{T}}^{A, b, d}$, such that $t\in [\check{t}^{l'}, \hat{t}]$, i.e., $\check{t}^{l'}\leq t\leq\hat{t}$. Thus,

Let us note that $l'\in \{1, 2, \cdots, s\}$. The inequalities (3.2) and (3.3) imply that $z^{*}\leq z(t)$, i.e., $z(\check{t}^{l^{*}})\leq z(t)$. As a result, $\check{t}^{l^{*}}$ is an optimal solution of (1.3). □

It has been shown in Theorem 3 that the optimal solution of problem (1.3) should exist when system (1.2) is consistent. Next, we consider the resolution of problem (1.3) with the assumption that $\mathcal{T}^{A, b, d}\neq\emptyset$.

Based on the maximum solution $\hat{t}$ and the formulae in problem (1.3), we construct the following single-constraint programming problem:

for each $i\in \mathcal{I}$. Then, we obtain $m$ subproblems, denoted by $\{(P_{1}), (P_{2}), \cdots, (P_{m})\}$, corresponding to the original problem (1.3).

In fact, the optimal solution of problem (1.3) can be generated by the optimal solutions of these subproblems, as indicated in what follows. Next, we provide an algorithm to obtain the optimal solution of each subproblem, and then we show the relationship between the original problem (1.3) and the subproblems $\{(P_{1}), (P_{2}), \cdots, (P_{m})\}$.

3.2.   Algorithm for obtaining an optimal solution to subproblem $(P_{i})$

Let $i\in \mathcal{I}$ be an arbitrary index in $\mathcal{I}$. In this subsection, we propose an effective approach to obtain an optimal solution of subproblem $(P_{i})$, i.e., problem (3.4). In the remainder of this subsection, we always assume that $i$ is a given index.

We denote the index set as

It is clear that $j\in \mathcal{J}^{\hat{t}}_{i}$ if and only if $a_{ij}\wedge\hat{t}_{j}\geq b_{i}$.

Proposition 2. $\hat{t}$ is a solution of system (1.2), if and only if $\mathcal{J}^{\hat{t}}_{k}\neq\emptyset$ holds for any $k\in \mathcal{I}$.

Proof. ($\Rightarrow$) If $\hat{t}$ is a solution of system (1.2), we have

Hence, there exists $j'\in \mathcal{J}$ such that $a_{kj'}\wedge\hat{t}_{j'} \geq b_{k}$. This implies that $j'\in \mathcal{J}^{\hat{t}}_{k}$, i.e., $\mathcal{J}^{\hat{t}}_{k}\neq\emptyset$.

($\Leftarrow$) If $\mathcal{J}^{\hat{t}}_{k}\neq\emptyset$, $\forall k\in \mathcal{I}$, then there exists $j_{k}\in \mathcal{J}^{\hat{t}}_{k}$ for each $k$. Since $j_{k}\in \mathcal{J}^{\hat{t}}_{k}\subseteq\mathcal{J}$, by (3.5) we have

Therefore, $\hat{t}$ is a solution of system (1.2). □

According to Theorem 1 and Proposition 2, we find Corollary 1.

Corollary 1. $\mathcal{T}^{A, b, d}\neq\emptyset$ if and only if $\mathcal{J}^{\hat{t}}_{k} neq\emptyset$ holds for any $k\in \mathcal{I}$.

Obviously, Corollary 1 can also be used to check the consistency of system (1.2) through the index sets $\{\mathcal{J}^{\hat{t}}_{1}, \mathcal{J}^{\hat{t}}_{2}, \cdots, \mathcal{J}^{\hat{t}}_{m}\}$.

Based on the index set $\mathcal{J}^{\hat{t}}_{i}$, defined by (3.5), we find the optimal index as

Then we have $p^{*}_{i}\in \mathcal{J}^{\hat{t}}_{i}$ and $c_{p^{*}_{i}} = \min\{c_{j}|j\in \mathcal{J}^{\hat{t}}_{i}\}$. Furthermore, we construct the vector $t^{*i} = (t^{*i}_{1}, t^{*i}_{2}, \cdots, t^{*i}_{n})$ as

We show that the vector $t^{*i}$ is indeed an optimal solution of the subproblem $(P_{i})$.

Theorem 4. (Optimal solution of $(P_{i})$) Let us suppose $\mathcal{T}^{A, b, d}\neq\emptyset$. Then, the vector $t^{*i}$ defined above is an optimal solution of the subproblem $(P_{i})$.

Proof. (Feasibility) Let $j' = p^{*}_{i}\in \mathcal{J}^{\hat{t}}_{i}$. By (3.5), we have

By (3.9), we also have

and

Since $a_{ij'}\geq b_{i}$, it is immediate that $a_{ij'}\wedge b_{i} = b_{i}$. Considering (3.12), we have

According to (3.10)–(3.12), we have

and

Formulae (3.14) and (3.15) imply that $t^{*i}\leq \hat{t}$. Combining formula (3.13), $t^{*i}$ is a feasible solution of subproblem $(P_{i})$.

According to (3.11) and (3.12), $z(t^{*i}) = c_{j'}b_{i}$. Let us take an arbitrary feasible solution of (1.3) as $t$. Then, it holds that

There exists $j''\in \mathcal{J}$ such that $a_{ij''}\wedge t_{j''} \geq b_{i}$, i.e., $a_{ij''} \geq b_{i}$ and $t_{j''} \geq b_{i}$. By (3.5), we have $j''\in \mathcal{J}^{\hat{t}}_{i}$. Since $j' = p^{*}_{i}$, by (3.8) we have

However, considering $t_{j''} \geq b_{i}$, we have

As a consequence, $t^{*i}$ is an optimal solution of subproblem $(P_{i})$. □

Summarizing the above results, we develop Algorithm Ⅰ to solve subproblem $(P_{i})$.

Algorithm Ⅰ: To calculate an optimal solution of the subproblem $(P_{i})$

Step 1: Construct the vector $\hat{t} = (\hat{t}_{1}, \hat{t}_{2}, \cdots, \hat{t}_{n})$ following (2.2).

Step 2: Apply the vector $\hat{t}$; check the consistency of system (1.2) following Theorem 1. If $\hat{t}\in \mathcal{T}^{A, b, d}$, then $\mathcal{T}^{A, b, d}\neq\emptyset$ and problem (1.3) is solvable. Continue to the next step. Otherwise, problem (1.3) is unsolvable; stop.

Step 3: Find the index set $\mathcal{J}^{\hat{t}}_{i}$ according to (3.5).

Step 4: Find the optimal index $p^{*}_{i}$ according to $\mathcal{J}^{\hat{t}}_{i}$ and (3.8).

Step 5: Find the vector $t^{*i} = (t^{*i}_{1}, t^{*i}_{2}, \cdots, t^{*i}_{n})$ according to the optimal indices $p^{*}_{i}$ and (3.9). Then, by Theorem 4, $t^{*i}$ is an optimal solution of subproblem $(P_{i})$.

Example 1. Let us consider the following single-constraint programming problem:

Algorithm Ⅰ is applied to find an optimal solution to problem (3.19), i.e., problem $(P_{0})$.

Solution. Steps 1 and 2: The constraint is extracted from system (4.1) appearing in Example 2 below. We verify that system (4.1) is consistent, with the maximum solution $\hat{t} = (0.76, 0.77, 0.76, 0.75, 0.85, 1)$. Hence, we go directly to Step 3.

Step 3: Since

by (3.5) we have $\mathcal{J}^{\hat{t}}_{0} = \{1, 2, 3, 6\}$.

Step 4: Here, $c = (0.4, 0.5, 0.7, 0.3, 0.5, 0.6)$. Since

by (3.8), we find the optimal index as $p^{*}_{0} = 1$.

Step 5: Since $p^{*}_{0} = 1$, we find the vector $t^{*0}$ by (3.9) as $t^{*0} = (0.38, 0, 0, 0, 0, 0)$. According to Theorem 4, $t^{*0} = (0.38, 0, 0, 0, 0, 0)$ is an optimal solution of subproblem $(P_{0})$, i.e., problem (3.19). □

3.3.   The SCP-based algorithm for solving problem (1.3)

In Subsection 3.2, we find an optimal solution for each subproblem $(P_{i})$, denoted by $t^{*i}$. Based on these optimal solutions $\{t^{*1}, t^{*2}, \cdots, t^{*m}\}$, we generate the optimal solution of problem (1.3) in this subsection.

For $x^{1} = (x^{1}_{1}, \cdots, x^{1}_{n}), x^{2} = (x^{2}_{1}, \cdots, x^{2}_{n})\in [0, 1]^{n}$, let

Lemma 1. For arbitrary $x^{1}, x^{2}, \cdots, x^{m}\in [0, 1]^{n}$, we have $z(x^{1}\vee x^{2}\vee\cdots\vee x^{m}) = z(x^{1})\vee z(x^{2})\vee\cdots\vee z(x^{m})$.

Proof. In fact, we have to prove only that $z(x^{1}\vee x^{2}) = z(x^{1})\vee z(x^{2})$.

□

Lemma 2. Let $t\in [0, 1]$ be an arbitrary real number. Then, we have $t\in \mathcal{T}^{A, b, d}$ if and only if $A\circ t\geq b$ and $t\leq \hat{t}$.

Proof. ($\Rightarrow$) This is evident, according to Proposition 1 and the expression of system (1.2).

($\Leftarrow$) Let us consider, arbitrarily, $i'\in \mathcal{I}$ and $j'\in \mathcal{J}$. Let us recall that $\mathcal{I}_{j'} = \{i\in \mathcal{I}|a_{ij'} > d_{i}\}$.

If $i'\notin \mathcal{I}_{j'}$, then we have

If $i'\in \mathcal{I}_{j'}$, then by (2.2) we have $I_{j'}\neq\emptyset$ and $\hat{t}_{j'} = \bigwedge\limits_{i\in \mathcal{I}_{j'}} d_{i} \leq d_{i'}$. Thus,

Due to the arbitrariness of $i$ and $j$, we have

Hence,

That is, $A\circ \hat{t}\leq d$. Since $t\leq \hat{t}$, we have $A\circ t\leq A\circ \hat{t}\leq d$. Combining $A\circ t\geq b$, it is immediate that $t\in \mathcal{T}^{A, b, d}$. □

Theorem 5. Let $t^{*i}$ be an optimal solution of subproblem $(P_{i})$ for each $i\in \mathcal{I}$. Then, $t^{*} = t^{*1}\vee t^{*2} \vee\cdots\vee t^{*m}$ is an optimal solution of problem (1.3).

Proof. (Feasibility) For arbitrarily given $i\in \mathcal{I}$, we verified in Theorem 4 that $t^{*i}\leq \hat{t}$. Hence,

Since $t^{*} = t^{*1}\vee t^{*2} \vee\cdots\vee t^{*m}$, it is obvious that $t^{*}_{j} = \bigvee\limits_{k\in \mathcal{I}} t^{*k}_{j} \geq t^{*i}_{j}$, $\forall i\in \mathcal{I}, j\in \mathcal{J}$. Hence, by (3.13),

That is, $A\circ t^{*}\geq b$. Considering $t^{*}\leq \hat{t}$, it follows from Lemma 2 that $t^{*}\in \mathcal{T}^{A, b, d}$. That is, $t^{*}$ is a feasible solution to problem (1.3).

(Optimality) Let $t\in \mathcal{T}^{A, b, d}$ be an arbitrary feasible solution of problem (1.3). By observing system (1.2), it is clear that

Moreover, by Proposition 1, we have $t\leq \hat{t}$. Hence, $t$ is a feasible solution of subproblem $(P_{i})$ for any $i\in \mathcal{I}$. Let us note that $t^{*i}$ is the optimal solution of $(P_{i})$. We have

Following Lemma 1, we have

As a consequence, $t^{*}$ is an optimal solution of problem (1.3). □

According to Theorem 5, if we can determine the optimal solutions of all the subproblems $\{P_{1}, P_{2}, \cdots, P_{m}\}$, then the optimal solution of problem (1.3) can be generated by those $m$ optimal solutions. The resolution approach indicated in Theorem 5 is based on single-constraint programming (SCP), i.e., subproblems $\{P_{1}, P_{2}, \cdots, P_{m}\}$. Thus, we call this the SCP-based resolution approach. Moreover, we summarize the resolution approach as the following SCP-based algorithm.

SCP-based Algorithm to obtain an optimal solution of problem (1.3)

Step 1: Construct the vector $\hat{t} = (\hat{t}_{1}, \hat{t}_{2}, \cdots, \hat{t}_{n})$ following (2.2).

Step 2: Apply the vector $\hat{t}$; check the consistency of system (1.2) following Theorem 1. If $\hat{t}\in \mathcal{T}^{A, b, d}$, then $\mathcal{T}^{A, b, d}\neq\emptyset$ and problem (1.3) is solvable. Continue to the next step. Otherwise, problem (1.3) is unsolvable; stop.

Step 3: Construct $m$ subproblems as (3.4), denoted by $\{(P_{1}), (P_{2}), \cdots, (P_{m})\}$.

Step 4: For each $i\in \mathcal{I}$, find an optimal solution of the subproblem $(P_{i})$ by applying the proposed Algorithm Ⅰ presented in Subsection 3.2. Suppose the obtained optimal solution of $(P_{i})$ is $t^{*i}$, $\forall i\in \mathcal{I}$. Then, find $m$ optimal solutions as $\{t^{*1}, t^{*2}, \cdots, t^{*m}\}$.

Step 5: Generate the vector $t^{*} = t^{*1}\vee t^{*2} \vee\cdots\vee t^{*m}$. Then, by Theorem 5, $t^{*}$ is an optimal solution of problem (1.3).

4.   Numerical example

In this section, we provide an illustrative example of our proposed SCP-based algorithm.

Example 2. We consider a P2P network system with 6 terminals. Let us suppose the P2P network system is described by the max-min FRI system as

where

$b = (0.45, 0.37, 0.52, 0.38, 0.42, 0.48)$, $d = (0.75, 0.78, 0.85, 0.76, 0.77, 0.89)$, $t = (t_{1}, t_{2}, \cdots, t_{6})$. We find an optimal solution of the following weighted minimax programming problem:

where $c = (c_{1}, c_{2}, \cdots, c_{6}) = (0.5, 0.6, 0.8, 0.4, 0.6, 0.7)$.

Solution. Step 1: According to $\mathcal{I}_{j} = \{i\in \mathcal{I}|a_{ij} > d_{i}\}$, $\mathcal{I}_{1} = \{2, 4\}$, $\mathcal{I}_{2} = \{5\}$, $\mathcal{I}_{3} = \{4\}$, $\mathcal{I}_{4} = \{1\}$, $\mathcal{I}_{5} = \{3\}$, and $\mathcal{I}_{6} = \emptyset$. Based on these index sets, we can calculate the vector $\hat{t}$ by (2.2). After calculation, we have $\hat{t} = (\hat{t}_{1}, \hat{t}_{2}, \cdots, \hat{t}_{6}) = (0.76, 0.77, 0.76, 0.75, 0.85, 1)$.

Step 2: We compute $A\circ \hat{t}$ as follows:

We know that $b\leq A\circ \hat{t}\leq d$, i.e., $\hat{t}$ fulfills system (4.1). Hence, system (4.1) is consistent, and problem (4.3) is solvable. We continue to the next step.

Step 3: Following (3.4), we construct the subproblems as follows.

Step 4: In this step, we apply our proposed Algorithm Ⅰ to find the optimal solutions of the subproblems $\{(P_{1}), (P_{2}), \cdots, (P_{6})\}$.

According to (3.5), we find the index sets as $\mathcal{J}^{\hat{t}}_{1} = \{2, 3, 4, 5, 6\}$, $\mathcal{J}^{\hat{t}}_{2} = \{1, 3, 5, 6\}$, $\mathcal{J}^{\hat{t}}_{3} = \{5, 6\}$, $\mathcal{J}^{\hat{t}}_{4} = \{1, 2, 3, 6\}$, $\mathcal{J}^{\hat{t}}_{5} = \{2, 3, 6\}$, and $\mathcal{J}^{\hat{t}}_{1} = \{2, 3, 5\}$.

Based on these index sets, we further compute the optimal indices by (3.8) as $p^{*}_{1} = 4$, $p^{*}_{2} = 1$, $p^{*}_{3} = 5$, $p^{*}_{4} = 1$, $p^{*}_{5} = 2$, and $p^{*}_{6} = 2$ or $5$.

As a result, we can find the optimal solutions $\{t^{*1}, t^{*2}, \cdots, t^{*6}\}$ following (3.9). Since $p^{*}_{1} = 4$, we find the optimal solution to $(P_{1})$ as

Since $p^{*}_{2} = 1$, we find the optimal solution to $(P_{2})$ as

Since $p^{*}_{3} = 5$, we find the optimal solution to $(P_{3})$ as

Since $p^{*}_{4} = 1$, we find the optimal solution to $(P_{4})$ as

Since $p^{*}_{5} = 2$, we find the optimal solution to $(P_{5})$ as

Since $p^{*}_{6} = 2$ or $5$, we find the optimal solution to $(P_{6})$ as

or

Step 5: We generate the vector $t^{*} = t^{*1}\vee t^{*2} \vee\cdots\vee t^{*6}$. When $t^{*6} = (0, b_{6}, 0, 0, 0, 0) = (0, 0.48, 0, 0, 0, 0)$, we have

When $t^{*6} = (0, 0, 0, 0, b_{6}, 0) = (0, 0, 0, 0, 0.48, 0)$, we have

According to Theorem 5, both $t^{*}$ and ${t^{*}}'$ are the optimal solutions of problem (4.3). □

5.   Comparing our problem and the proposed method to that in existing research

In this work, we establish a minimax program with max-min FRI constraints. Moreover, we propose the so-called SCP-based algorithm to identify an optimal solution. In the following section, we compare our problem and the proposed resolution algorithm to those presented in several existing works.

(ⅰ) The optimization problem investigated in this work has not been studied previously. This result is different from those reported in existing research.

In fact, minimax programming problems subject to addition-min FRIs were studied in ^{[11,12,13,14,15,16,17]}. In those problems, the optimization objective was a minimax function, but the constraints were the addition-min FRIs; they are different from those in our studied problem. Moreover, ^{[28,29,30,31,32,33,34]} minimized a linear objective function under the constraints of max-min FRIs, while ^{[18,19,35,36,37]} optimized a geometric objective function under the same constraints. Although the constraints are the same as those in our studied problem, the linear or geometric objective function is different from the minimax objective function, which appears in our problem. Consequently, our minimax programming problem with the addition-min FRI constraints is different from those presented in ^{[11,12,13,14,15,16,17,18,19,28,29,30,31,32,33,34,35,36,37]}.

(ⅱ) The feasible domain of our optimization model is different from those employed in some relevant published works.

In the minimax optimization problems studied in ^{[11,12,13,14,15,16,17]}, the feasible domain is the solution set to the addition-min FRIs. It has been formally proven that such a feasible domain is a convex set ^[2]. However, the feasible domain of our problem, i.e., the solution set to the max-min FRIs, should be nonconvex when the minimum is not unique ^[38]. In addition, a system of addition-min FRIs usually has infinitely many minimal solutions ^[2], in most cases. However, the number of minimal solutions to the max-min FRIs is always finite. Consequently, the properties of the feasible domain with an addition-min composition are much different from those with a max-min composition.

(ⅲ) The SCP-based algorithm is proposed for our optimization model; this approach is different from the existing resolution methods adopted for the relevant fuzzy relation optimization models in ^{[11,12,13,14,15,16,17,18,19,28,29,30,31,32,33,34,35,36,37]}.

In ^[15], the dichotomy algorithm was proposed for searching for optimal solutions. The subproblem and single-variable approach was also proposed in ^{[11,12,13,16,17]}. In addition, ^[14] developed the so-called optimal-vector-based algorithm for minimax programming with addition-min FRI constraints. However, the branch and bound method ^{[28,29,30,31,32,33,34]}, which is suitable for linear programming with max-min FRI constraints, and the value-matrix-based iterative method ^[35,36,37], which is suitable for geometric programming with max-min FRI constraints, are ineffective for our minimax programming problem with max-min FRI constraints. All of these existing methods for the relevant fuzzy relation optimization models are no longer effective for our problem due to their different optimization scenarios and properties of the feasible domains.

6.   Conclusions

The P2P network system has been reduced to the max-min FRIs, i.e., system (1.2). To decrease network congestion in the P2P network system, we constructed and investigated a weighted minimax programming problem subject to system (1.2), i.e., problem (1.3). The purpose of this work is to propose an effective algorithm to produce an optimal solution of (1.3). We divided the original problem (1.3) into $m$ subproblems. Each subproblem involves single-constraint programming. Algorithm Ⅰ was designed to find one of the optimal solutions of each subproblem. The optimal solution can be generated by the optimal solutions from those $m$ subproblems. We further proposed the SCP-based algorithm to find an optimal solution to the original problem (1.3). A numerical example was given to verify the validity of the SCP-based algorithm. Moreover, Example 2 showed that the optimal solutions might not be unique.

In the future, based on the max-min FRIs for modeling the P2P network system, we plan to further consider the stability with respect to some given solutions of the max-min FRIs.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (12271132) and the Guangdong Basic and Applied Basic Research Foundation (2024A1515010532, 2023A1515011093, 2022A1515011460, 2023KQNCX041, 2021ZDJS044, QD202211, PNB2103).

Conflict of interest

The authors declare that they have no conflict of interest.