Location-based reverse data delivery between infrastructure and vehicles

Farhan Khan; Sing Kiong Nguang; Farhan Khan; Sing Kiong Nguang

doi:10.3934/electreng.2021009

AIMS Electronics and Electrical Engineering

2021, Volume 5, Issue 2: 158-175. doi: 10.3934/electreng.2021009

Previous Article Next Article

Research article

Location-based reverse data delivery between infrastructure and vehicles

Farhan Khan ^,,
Sing Kiong Nguang

Department of Electrical, Computer, and Software Engineering, Faculty of Engineering, The University of Auckland, 20 Symonds Street, Auckland CBD, Auckland, New Zealand

Received: 26 January 2021 Accepted: 08 June 2021 Published: 10 June 2021

Reverse data delivery is one of the key operations in vehicular ad hoc networks which allows data delivery from roadside units (infrastructure) to vehicles. In the past, a number of data dissemination schemes have been proposed by researchers for the vehicular ad hoc networks to tackle the problem of data forwarding from vehicles and roadside units to data concentration points or Access Points (APs). In contrast, schemes for reverse data forwarding which allows a data concentration point to apprise the on-road vehicles about any eventuality or developing hazardous conditions are very few. This paper proposes a reverse data forwarding scheme which utilizes the characteristics of the road networks to inform passing vehicles of important information related to any accident, crash, or hazardous road conditions. The proposed scheme takes into account the geographical proximity factor by considering a localized sub-region/segment in the greater road network which is most adversely affected by the occurrence of some unfortunate road event. For its implementation, the scheme is dependent on DSRC-enabled roadside equipment to relay road-safety messages from AP to vehicles. In case if the passing vehicles are not fitted with DSRC on-board units, the scheme has the capability to directly interact with the variable-message signs on intersections with the objective of reaching as many vehicles as possible to increase the chances of message delivery. Simulation results using a small road segment confirm that the proposed scheme is more effective when the localized sub-region is smaller or in other words when more vehicles in the vicinity of the accident location are provided with pre-warning messages.

Keywords:

Citation: Farhan Khan, Sing Kiong Nguang. Location-based reverse data delivery between infrastructure and vehicles[J]. AIMS Electronics and Electrical Engineering, 2021, 5(2): 158-175. doi: 10.3934/electreng.2021009

Related Papers:

[1]	Hongwu Li, Yuling Feng, Hongwei Jiao, Youlin Shang . A novel algorithm for solving sum of several affine fractional functions. AIMS Mathematics, 2023, 8(4): 9247-9264. doi: 10.3934/math.2023464
[2]	Hongwu Li, Longfei Wang, Yingfeng Zhao . Global optimization algorithm for a class of linear ratios optimization problem. AIMS Mathematics, 2024, 9(6): 16376-16391. doi: 10.3934/math.2024793
[3]	Junqiao Ma, Hongwei Jiao, Jingben Yin, Youlin Shang . Outer space branching search method for solving generalized affine fractional optimization problem. AIMS Mathematics, 2023, 8(1): 1959-1974. doi: 10.3934/math.2023101
[4]	Bo Zhang, Yuelin Gao, Ying Qiao, Ying Sun . A nonlinear relaxation-strategy-based algorithm for solving sum-of-linear-ratios problems. AIMS Mathematics, 2024, 9(9): 25396-25412. doi: 10.3934/math.20241240
[5]	Xiaoli Huang, Yuelin Gao . An efficient outer space branch-and-bound algorithm for globally minimizing linear multiplicative problems. AIMS Mathematics, 2023, 8(11): 26045-26069. doi: 10.3934/math.20231327
[6]	Regina S. Burachik, Bethany I. Caldwell, C. Yalçın Kaya . Douglas–Rachford algorithm for control- and state-constrained optimal control problems. AIMS Mathematics, 2024, 9(6): 13874-13893. doi: 10.3934/math.2024675
[7]	Murat A. Sultanov, Vladimir E. Misilov, Makhmud A. Sadybekov . Numerical method for solving the subdiffusion differential equation with nonlocal boundary conditions. AIMS Mathematics, 2024, 9(12): 36385-36404. doi: 10.3934/math.20241726
[8]	Cuijie Zhang, Zhaoyang Chu . New extrapolation projection contraction algorithms based on the golden ratio for pseudo-monotone variational inequalities. AIMS Mathematics, 2023, 8(10): 23291-23312. doi: 10.3934/math.20231184
[9]	Hengdi Wang, Jiakang Du, Honglei Su, Hongchun Sun . A linearly convergent self-adaptive gradient projection algorithm for sparse signal reconstruction in compressive sensing. AIMS Mathematics, 2023, 8(6): 14726-14746. doi: 10.3934/math.2023753
[10]	Sema Akin Bas, Beyza Ahlatcioglu Ozkok . An iterative approach for the solution of fully fuzzy linear fractional programming problems via fuzzy multi-objective optimization. AIMS Mathematics, 2024, 9(6): 15361-15384. doi: 10.3934/math.2024746

Abstract

1. Introduction

In this paper, we consider the following sum of affine ratios problem (where SARP is sum of affine ratios problem):

$\operatorname{(SARP):}\left\{\begin{array}{ll} \quad \min H(x) = \sum\limits_{i = 1}^{p}\frac {\sum\limits_{j = 1}^{n}c_{ij}x_{j}+f_{i}}{\sum\limits_{j = 1}^{n}d_{ij}x_{j}+g_{i}}, \\ \ \text { s.t. } x\in D = \left\{x \in \mathbb{R}^{n} \mid A x \leq b, x\geq 0\right\}, \end{array}\right.$

where $A$ is an $m\times n$ order real matrix and $b$ is an $m$ dimension column vector. $D\neq\emptyset$ , $c_{ij}, d_{ij}\in \mathbb{R}^{n}$ , and $f_{i}, g_{i}\in \mathbb{R}$ . The denominator of each ratio

$\sum\limits_{j = 1}^{n}d_{ij}x_{j}+g_{i}\neq0$

over $D$ . Due to

$\sum\limits_{j = 1}^{n}d_{ij}x_{j}+g_{i}\neq0$

and the continuity of the ratio

$\frac {\sum\limits_{j = 1}^{n}c_{ij}x_{j}+f_{i}}{\sum\limits_{j = 1}^{n}d_{ij}x_{j}+g_{i}},$

we can obtain that

$\sum\limits_{j = 1}^{n}d_{ij}x_{j}+g_{i} < 0$

$\sum\limits_{j = 1}^{n}d_{ij}x_{j}+g_{i} > 0.$

$\sum\limits_{j = 1}^{n}d_{ij}x_{j}+g_{i} < 0,$

letting

$\frac{\sum\limits_{j = 1}^{n}c_{ij}x_{j}+f_{i}}{\sum\limits_{j = 1}^{n}d_{ij}x_{j}+g_{i}} = \frac{-\Big(\sum\limits_{j = 1}^{n}c_{ij}x_{j}+f_{i}\Big)}{-\Big(\sum\limits_{j = 1}^{n}d_{ij}x_{j}+g_{i}\Big)},$

it is obvious that

$-\Big(\sum\limits_{j = 1}^{n}d_{ij}x_{j}+g_{i}\Big) > 0.$

Therefore, without loss of generality, we assume that

$\sum\limits_{j = 1}^{n}d_{ij}x_{j}+g_{i} > 0$

always holds.

The SARP is a specific class of fractional programming problem. It has a wide range of applications in laminate manufacturing ^[1,2], portfolio optimization ^[3,4,5], finance and investment ^[6], computer vision ^[7], system engineering ^[8], information theory ^[9], material layout ^[10,11], and so on. In addition, it is obvious that the objective function of the SARP is neither quasi-convex nor quasi-concave, which is extremely challenging in terms of theory and computation. Thus, the research on the approach to solve the SARP has both theoretical and practical significance value.

Up to now, a number of methods have been developed to solve the SARP. On the basis of the characteristics of the algorithms in each literature, it can be roughly separated into the following categories: the parametric simplex methods ^[12,13], the unified monotonic approach ^[14], the interior-point method ^[15,16], the image space analysis method ^[17], the trapezoidal branching searching algorithm ^[18], the branch-and-bound algorithms ^[19,20,21], and so on. It should be noted that the algorithms in the above references ^[19,20,21] can either only solve special forms of the SARP or the SARP with fewer variables. Recently, by exploiting equivalent transformation and the characteristics of general single ratio functions, Jiao and Ma ^[22] combined the acceleration technique to develop an efficient outer space rectangular branch-and-bound algorithm. Jiao et al. ^[23] put forward a practical algorithm for minimizing the SARP. In the same year, by using the equivalent conversion and linearization method, Jiao et al. ^[24] presented an effective branch-and-bound algorithm for the SARP. Meanwhile, Jiao et al. ^[25] also designed an image space branch-reduction-bound algorithm for globally solving the SARP. It should be emphasized that references ^[23,24,25] proposed several outer space branch-and-bound algorithms for the problem (SARP), and the partitioning spaces of these branch-and-bound algorithms all occur in the $p$ -dimensional outer space. In addition, Pei and Zhu ^[26] designed a convex relaxation algorithm for maximizing the sum of the difference of convex functions ratios problems based on the branch-and-bound framework. Kuno ^[27] presented a trapezoidal branch-and-bound algorithm to solve the SARP. Based on the algorithm of Kuno ^[27], Shen et al. ^[28] proposed an accelerating trapezoidal branch-reduction-bound algorithm for globally solving the sum of linear ratios problems. By constructing the new accelerating technique, Jiao and Liu ^[29] developed a branch-reduction-bound algorithm for the sum of quadratic ratios problems. Especially, the literatures ^[30,31] provided for the first time an outer space branch-relaxation-bound algorithm for generalized linear fractional programming problems and generalized affine multiple product programming problems, respectively. However, the above-reviewed methods only deal with some particular forms of the SARP or are difficult to solve the SARP with large-scale variables. Therefore, it is still necessary to propose a practical efficient algorithm for addressing the general form of the SARP.

The main purpose of this paper is to design an effective outcome space branch-and-bound algorithm to globally solve the SARP. Initially, we employ two equivalence conversions to transform the SARP into an equivalent problem ( $\rm EP_{3}$ ). Subsequently, we design a linearization technique that is used to construct the affine relaxation problem (ARP) of the problem ( $\rm EP_{3}$ ). Based on the ARP and the branch-and-bound framework, we present an outcome space branch-and-bound algorithm. Ultimately, the numerical experimental results demonstrate that our algorithm is feasible. In addition, the branch search process in this paper occurs in the $(p-1)$ -dimensional outer space, which makes the computational cost much lower. Compared with other methods that take place in the $n$ -dimension or $p$ -dimensional space, our method is more efficient. Furthermore, the algorithm is shown to converge to a global optimal solution of the SARP eventually. Meanwhile, the computational complexity of the algorithm is deduced in detail.

The overall structure of the study adopts the format of six sections, including this introductory section. In Section 2, we convert the SARP to an equivalent problem ( $\rm EP_{3}$ ) and construct its affine relaxation programming problem. In Section 3, we design an outcome space branch-and-bound algorithm for globally solving the SARP, prove the convergence of the algorithm, and derive the derivation of the computational complexity. In Section 4, a comparison of the numerical experimental results indicates that the presented algorithm is reliable. Finally, some concluding remarks are given in Section 5.

2. Equivalence transformation and its affine relaxation programming

2.1. Equivalent transformation

To tackle the SARP globally, we transform the original problem (SARP) into an equivalence problem as below. For each $x\in D$ , let

$t = \frac{1}{\sum\limits_{j = 1}^{n}d_{pj}x_{j}+g_{p}}$

and

$z_{j} = tx_{j}.$

By utilizing the well-known Charnes-Cooper transformation ^[32], the SARP can be rewritten as problem ( $\rm EP_{1}$ ), as shown below.

${\rm{(EP_{1}):}}\left\{ \begin{array}{ll} \quad \min \hat{H}(t, z) = \sum\limits_{i = 1}^{p-1}\frac{\sum\limits_{j = 1}^{n}c_{ij}z_{j}+f_{i}t}{\sum\limits_{j = 1}^{n}d_{ij}z_{j}+g_{i}t}+\sum\limits_{j = 1}^{n}c_{pj}z_{j}+f_{p}t, \\ \text{s.t. } \sum\limits_{j = 1}^{n}d_{pj}z_{j}+g_{p}t = 1,\\ \quad A z \leq bt,\ t\geq 0,\ z\geq 0. \end{array} \right.$

At this time, the index set becomes $i\in\{1, 2, \ldots, p-1\}$ , and let

$\chi = \{(t, z) \in \mathbb{R}^{n+1}| \sum\limits_{j = 1}^{n}d_{pj}z_{j}+g_{p}t = 1,\ \ A z \leq bt, t\geq 0, z\geq 0\},$

where the set $\chi$ is non-empty and bounded.

Then we focus on the following equivalence conversion, for each $i\in\{1, 2, \ldots, p-1\}$ , by introducing the variable

$s_{i} = \frac{1}{\sum\limits_{j = 1}^{n}d_{ij}z_{j}+g_{i}t},$

the lower bound

$\underline s_{i}^{0} = \min\limits_{(t, z) \in \chi}\frac{1}{\sum\limits_{j = 1}^{n}d_{ij}z_{j}+g_{i}t}$

and upper bound

$\overline s_{i}^{0} = \max\limits_{(t, z) \in \chi}\frac{1}{\sum\limits_{j = 1}^{n}d_{ij}z_{j}+g_{i}t}$

can be calculated, and we can obtain the initial rectangle

$S^{0} = [\underline s^{0},\overline s^{0}],$

where

$\underline s^{0} = (\underline s_{1}^{0}, \underline s_{2}^{0}, \ldots, \underline s_{p-1}^{0})$

and

$\overline s^{0} = (\overline s_{1}^{0}, \overline s_{2}^{0}, \ldots, \overline s_{p-1}^{0}).$

Further, the problem ( $\rm EP_{1}$ ) can be reduced into the problem ( $\rm EP_{2}$ ) by the variable $s_{i}$ as follows:

${\rm{(EP_{2}):}}\left\{ \begin{array}{ll} \min\ \Phi(s, t, z) = \sum\limits_{i = 1}^{p-1}s_{i}\Big(\sum\limits_{j = 1}^{n}c_{ij}z_{j}+f_{i}t\Big)+\sum\limits_{j = 1}^{n}c_{pj}z_{j}+f_{p}t, \\ \quad \text{s.t. } s_{i} = \frac{1}{\sum\limits_{j = 1}^{n}d_{ij}z_{j}+g_{i}t},\ \ i = 1,\ldots, p-1,\\ \quad (t, z)\in\chi, s\in S^{0}. \end{array} \right.$

Remark 1. If $(t^{*}, z^{*})$ is a global optimal solution of the problem ( $\rm EP_{1}$ ), then $(s^{*}, t^{*}, z^{*})$ is a global optimal solution of the problem ( $\rm EP_{2}$ ) with

$s_{i}^{*} = \frac{1}{\sum\limits_{j = 1}^{n}d_{ij}z^{*}_{j}+g_{i}t^{*}}, i = 1,2, \ldots, p-1.$

Conversely, if $(s^{*}, t^{*}, z^{*})$ is a global optimal solution of the problem ( $\rm EP_{2}$ ), then $(t^{*}, z^{*})$ is a global optimal solution of the problem ( $\rm EP_{1}$ ). In addition, the global optimal value of the problems ( $\rm EP_{1}$ ), ( $\rm EP_{2}$ ), and (SARP) are equal.

Based on

$\sum\limits_{j = 1}^{n}d_{ij}z_{j}+g_{i}t\neq0,$

the problem ( $\rm EP_{2}$ ) can be rewritten as the following equivalent form:

${\rm{(EP_{3}):}}\left\{ \begin{array}{ll} \quad \min \Phi(s, t, z) = \sum\limits_{i = 1}^{p-1}s_{i}\Big(\sum\limits_{j = 1}^{n}c_{ij}z_{j}+f_{i}t\Big)+\sum\limits_{j = 1}^{n}c_{pj}z_{j}+f_{p}t \\ \text{s.t. } s_{i}\Big(\sum\limits_{j = 1}^{n}d_{ij}z_{j}+g_{i}t\Big) = 1,\ \ i = 1,\cdots, p-1,\\ \quad (t, z)\in\chi, s\in S^{0}. \end{array} \right.$

Define $S$ to be $S^{0}$ or a sub-rectangle of $S^{0}$ , where

$S = [\underline s,\overline s]\subseteq [\underline s^{0},\overline s^{0}],\ \ \ \underline s = (\underline s_{1}, \underline s_{2}, \ldots, \underline s_{p-1})\geq \underline s^{0}$

and

$\overline s = (\overline s_{1}, \overline s_{2}, \ldots, \overline s_{p-1})\leq\overline s^{0}.$

2.2. Affine relaxation programming

For any $S\subseteq S^{0}$ , we construct the affine relaxation programming problem of the problem ( $\rm EP_{3}$ ) over $S$ as follows:

First, investigating the objective function, we can follow that

$\begin{align} \begin{array}{ll} \sum\limits_{i = 1}^{p-1}s_{i}\Big(\sum\limits_{j = 1}^{n}c_{ij}z_{j}+f_{i}t\Big) \geq & \sum\limits_{i = 1}^{p-1}\Big(\sum\limits_{j = 1, c_{ij} > 0}^{n}c_{ij}\underline s_{i}z_{j}+\sum\limits_{j = 1, c_{ij} < 0}^{n}c_{ij}\overline s_{i}z_{j}\Big) +\sum\limits_{i = 1,f_{i} > 0}^{p-1}f_{i}\underline s_{i}t+\sum\limits_{i = 1,f_{i} < 0}^{p-1}f_{i}\overline s_{i}t. \end{array} \end{align}$

(1)

Hence, we reformulate the objective function of the problem ( $\rm EP_{3}$ ) as

$\Phi^{R}(s, t, z) = \sum\limits_{i = 1}^{p-1}\Big(\sum\limits_{j = 1, c_{ij} > 0}^{n}c_{ij}\underline s_{i}z_{j}+\sum\limits_{j = 1, c_{ij} < 0}^{n}c_{ij}\overline s_{i}z_{j}\Big) +\sum\limits_{i = 1,f_{i} > 0}^{p-1}f_{i}\underline s_{i}t+\sum\limits_{i = 1,f_{i} < 0}^{p-1}f_{i}\overline s_{i}t+\sum\limits_{j = 1}^{n}c_{pj}z_{j}+f_{p}t.$

Next, investigating the constrained function, for any $i\in\{1, 2, \cdots, p-1\}, s \in S\subseteq S^{0}$ , define

$\begin{align*} \Psi_{i}(s_{i}, t, z)& = s_{i}\Big(\sum\limits_{j = 1}^{n}d_{ij}z_{j}+g_{i}t\Big)\\& = \sum\limits_{j = 1}^{n}d_{ij}s_{i}z_{j}+g_{i}s_{i}t,\\ \underline{G}_{i}& = \left\{ \begin{array}{ll} g_{i}\underline s_{i}, \ \ \mbox{if}\ g_{i} > 0,\\ g_{i}\overline s_{i}, \ \ \mbox{if}\ g_{i} < 0, \end{array} \right.\\ \overline{G}_{i}& = \left\{ \begin{array}{ll} g_{i}\underline s_{i}, \ \ \mbox{if}\ g_{i} < 0,\\ g_{i}\overline s_{i}, \ \ \mbox{if}\ g_{i} > 0, \end{array} \right. \end{align*}$

and

$\begin{align} \underline{\Psi}_{i}(\underline s_{i}, \overline s_{i}, t, z) = \sum\limits_{j = 1,d_{ij} > 0}^{n}d_{ij}\underline s_{i}z_{j}+\sum\limits_{j = 1,d_{ij} < 0}^{n}d_{ij}\overline s_{i}z_{j}+\underline{G}_{i}t, \end{align}$

(2)

$\begin{align} \overline{\Psi}_{i}(\underline s_{i}, \overline s_{i}, t, z) = \sum\limits_{j = 1,d_{ij} > 0}^{n}d_{ij}\overline s_{i}z_{j}+\sum\limits_{j = 1,d_{ij} < 0}^{n}d_{ij}\underline s_{i}z_{j}+\overline{G}_{i}t. \end{align}$

(3)

Clearly, for any $i\in \{1, 2, \ldots, p-1\}$ , we have that

$\underline{\Psi}_{i}(\underline s_{i}, \overline s_{i}, t, z)\leq \Psi_{i}(s_{i}, t, z)\leq \overline{\Psi}_{i}(\underline s_{i}, \overline s_{i}, t, z)$

always hold.

Integrating (1)–(3), for any $i\in \{1, 2, \ldots, p-1\}$ , the affine relaxation programming problem of the problem ( $\rm EP_{3}$ ) over $S$ is constructed as below:

${\rm{(ARP):}}\left\{ \begin{array}{ll} \min\ \Phi^{R}(s, t, z)\\ \text{s.t. } \underline{\Psi}_{i}(\underline s_{i}, \overline s_{i}, t, z) \leq 1,\ \ i = 1,\cdots, p-1,\\ \quad \overline{\Psi}_{i}(\underline s_{i}, \overline s_{i}, t, z)\geq 1,\ \ i = 1,\cdots, p-1,\\ (t, z)\in\chi, s\in S. \end{array} \right.$

By the construction process of the ARP, it is obvious that the optimal solution of the ARP provides a valid lower bound for that of the $\rm EP_{3}$ over $S^{0}$ .

Theorem 1. For each $i\in \{1, 2, \ldots, p-1\}$ , we have

$\Big|\Psi_{i}(s_{i}, t, z)-\underline{\Psi}_{i}(\underline s_{i}, \overline s_{i}, t, z)\Big|\rightarrow 0\ \ \mbox{and}\ \Big|\overline{\Psi}_{i}(\underline s_{i}, \overline s_{i}, t, z)-\Psi_{i}(s_{i}, t, z)\Big|\rightarrow 0\ \ \mbox{as}\ \ |\overline s_{i}-\underline s_{i}| \rightarrow 0,$

where " $\rightarrow$ " means "approaching".

Proof. Based on the previous definitions of the functions $\underline{\Psi}_{i}(\underline s_{i}, \overline s_{i}, t, z)$ , $\Psi_{i}(s_{i}, t, z)$ , and $\overline{\Psi}_{i}(\underline s_{i}, \overline s_{i}, t, z)$ , for any $(t, z)\in \chi, s_{i}\in [\underline s_{i}, \overline s_{i}]$ , we have that

$\begin{align*} \left|\Psi_{i}(s_{i}, t, z)-\underline{\Psi}_{i}(\underline s_{i}, \overline s_{i}, t, z)\right| \leq& \left|\overline{\Psi}_{i}(\underline s_{i}, \overline s_{i}, t, z)-\underline{\Psi}_{i}(\underline s_{i}, \overline s_{i}, t, z)\right|\\ = &\bigg|\sum\limits_{j = 1,d_{ij} > 0}^{n}d_{ij}\overline s_{i}z_{j}+\sum\limits_{j = 1,d_{ij} < 0}^{n}d_{ij}\underline s_{i}z_{j}+\overline{G}_{i}t\\&-\bigg(\sum\limits_{j = 1,d_{ij} > 0}^{n}d_{ij}\underline s_{i}z_{j}+\sum\limits_{j = 1,d_{ij} < 0}^{n}d_{ij}\overline s_{i}z_{j}+\underline{G}_{i}t\bigg)\bigg|\\ = &\sum\limits_{j = 1}^{n}|d_{ij}||\overline s_{i}-\underline s_{i}|z_{j}+|g_{i}||\overline s_{i}-\underline s_{i}|t\\ = &|\overline s_{i}-\underline s_{i}|\bigg(\sum\limits_{j = 1}^{n}|d_{ij}|z_{j}+|g_{i}|t\bigg). \end{align*}$

Since $\sum\limits_{j = 1}^{n}d_{ij}z_{j}+g_{i}t$ is a bounded function, we have

$\Big|\Psi_{i}(s_{i}, t, z)-\underline{\Psi}_{i}(\underline s_{i}, \overline s_{i}, t, z)\Big|\rightarrow 0\ \mbox{as}\ |\overline s_{i}-\underline s_{i}|\rightarrow 0.$

Similarly, we demonstrate

$\Big|\overline{\Psi}_{i}(\underline s_{i}, \overline s_{i}, t, z)-\Psi_{i}(s_{i}, t, z)\Big|\rightarrow 0\ \ \mbox{as}\ |\overline s_{i}-\underline s_{i}|\rightarrow 0,$

and the proof of the theorem is accomplished. □

From Theorem 1, it follows that the functions $\underline{\Psi}_{i}(\underline s_{i}, \overline s_{i}, t, z)$ and $\overline{\Psi}_{i}(\underline s_{i}, \overline s_{i}, t, z)$ can infinitely approximate the function $\Psi_{i}(s_{i}, t, z)$ as $|\overline s_{i}-\underline s_{i}|\rightarrow 0$ , which guarantees the global convergence of the outcome space branch-and-bound algorithm.

3. Algorithm and its computational complexity

An outcome space branch-and-bound method is provided in this part to resolve the SARP based on the previous ARP. By resolving a series of ARPs over the initial rectangle $S^{0}$ or a partitioned sub-rectangle of $S^{0}$ , the algorithm is able to acquire a global optimal solution. The simplest standard rectangle bisection rule, which is provided as follows, is designated in the proposed algorithm.

(1) Let

$\overline s_{\upsilon}^{k}-\underline s_{\upsilon}^{k} = \max \left\{\overline s_{i}^{k}-\underline s_{i}^{k}, i = 1,2, \ldots, p-1\right\}$

and

$s_{\upsilon}^{k} = \frac{l_{\upsilon}^{k}+u_{\upsilon}^{k}}{2}.$

(2) Let

$\widehat{s} = \left(s_{1}^{k}, s_{2}^{k}, \ldots, s_{\upsilon-1}^{k}, s_{\upsilon}^{k}, s_{\upsilon+1}^{k}, \ldots, s_{p-1}^{k}\right)^\top.$

The rectangle $S^{k}$ is split by the point $\widehat{s}$ into the following two rectangles:

$S^{k 1} = \prod\limits_{i = 1}^{\upsilon-1}\left[\underline s_{i}^{k}, \overline s_{i}^{k}\right] \times\left[\underline s_{\upsilon}^{k}, s_{\upsilon}^{k}\right] \times \prod\limits_{i = \upsilon+1}^{p-1}\left[\underline s_{i}^{k}, \overline s_{i}^{k}\right]$

and

$S^{k 2} = \prod\limits_{i = 1}^{\upsilon-1}\left[\underline s_{i}^{k}, \overline s_{i}^{k}\right] \times\left[s_{\upsilon}^{k}, \overline s_{\upsilon}^{k}\right] \times \prod\limits_{i = \upsilon+1}^{p-1}\left[\underline s_{i}^{k}, \overline s_{i}^{k}\right].$

3.1. Algorithm outline

The steps of the outcome space branch-and-bound algorithm for solving the SARP are described below:

Algorithm 1. Outcome space branch-and-bound algorithm.

Step 0. Given the convergence error $\epsilon\geq 0$ and the initial outer space rectangle

$S^{0} = \{s\in \mathbb{R}^{p-1}\mid \underline{s}_{i}^{0}\leq s_i\leq \overline{s}_{i}^{0},\ i = 1,2,\ldots,p-1\}.$

Solve the problem (ARP) over $S^{0}$ . If the problem (ARP) over $S^{0}$ is not feasible, then the problem (SARP) is not feasible, and the proposed algorithm stops.

Otherwise, we can obtain an optimal solution $(\hat{s}^{0}, t^{0}, z^{0})$ and the optimal value $LB(S^{0})$ of the problem (ARP) over $S^{0}$ . Let

$s^{0}_{i} = \frac{1}{\sum\limits_{j = 1}^{n}d_{ij}z^{0}_{j}+g_{i}t^{0}},\ \ i = 1,2,\ldots,p-1,$

then $(s^{0}, t^{0}, z^{0})$ is a feasible solution of the problem ( $\rm EP_{3}$ ). Let

$LB_{0} = LB(S^{0})$

and

$UB_{0} = \Phi(s^{0}, t^{0}, z^{0}).$

$UB_{0}-LB_{0}\leq\epsilon,$

then the algorithm stops executing, and $(s^{0}, t^{0}, z^{0})$ and $\frac{z^{0}}{t^{0}}$ are the global $\epsilon$ -optimal solutions of the problems ( $\rm EP_{3}$ ) and (SARP), respectively.

Otherwise, denote by the set of all active nodes $\Theta_{0} = \{S^{0}\}$ , denote by the set of the initial feasible point

$F = \{(s^{0}, t^{0}, z^{0})\},$

let $k = 0$ , and proceed to Step 1.

Step 1. Set

$UB_{k} = UB_{k-1}.$

Using the former branching rule, subdivide $S^{k}$ into two sub-rectangles $S^{k1}$ and $S^{k2}$ . Let

$Q = \{S^{k1},S^{k2}\}.$

Step 2. For each

$S^{k\tau}, \tau = 1,2,$

solve the problem (ARP) over $S^{k\tau}$ . If the problem (ARP) over $S^{k, \tau}$ is not feasible, then delete the rectangle $S^{k\tau}$ . Otherwise, we get the optimal solution $(\hat{s}(S^{k\tau}), t(S^{k\tau}), z(S^{k\tau}))$ and the optimal value $LB(S^{k\tau})$ of the problem (ARP) over $S^{k\tau}$ .

$UB_{k}\leq LB(S^{k\tau}),$

then let

$Q = Q\setminus \{S^{k\tau}\}.$

Otherwise, let

$s_{i}(S^{k\tau}) = \frac{1}{\sum\limits_{j = 1}^{n}d_{ij}z_{j}(S^{k\tau})+g_{i}t(S^{k\tau})}, \ \ i = 1,2,\ldots,p-1,$

update the feasible point set by

$F = F\bigcup\{(s(\Omega^{k\tau}), t(S^{k\tau}), z(S^{k,\tau}))\},$

let

$UB_{k} = \min \{UB_{k}, \Phi\big(s(S^{k\tau}), t(S^{k\tau}), z(S^{k,\tau})\big)\},$

and denote by the currently best feasible solution $(s^{k}, t^{k}, z^{k})$ , which corresponds to $UB_{k}$ .

Step 3. Set

$\Theta_{k} = (\Theta_{k}\setminus S^{k})\bigcup Q,$

update

$LB_{k} = \min\{LB(S)\mid S\in \Theta_{k}\},$

and let $S^{k}$ be the sub-rectangle which satisfies

$LB_{k} = LB(S^{k}).$

Step 4. If

$UB_{k}-LB_{k}\leq \epsilon,$

then the proposed algorithm stops, and $\frac{z^{k}}{t^{k}}$ and $(s^{k}, t^{k}, z^{k})$ are the $\epsilon$ -global optimal solutions of the problems (SARP) and ( $\rm EP_{3}$ ), respectively.

Otherwise, set $k = k+1$ , and go back to Step 1.

3.2. Convergence analysis

In this subsection, the global convergence of the proposed algorithm is discussed as follows:

Theorem 2. If Algorithm 1 ceases finite iterations, then the proposed algorithm will produce a globally optimal solution to the SARP. Otherwise, Algorithm 1 fails to terminate within a finite number of iterations, and it will produce an infinite sequence $\{x^{k}\}$ such that any accumulation point will be a global optimal solution of the SARP.

Proof. If Algorithm 1 ceases within a finite number of iterations, hypothesize that it is ceased at the $k_{th}$ iteration, denoted $LB_{k}$ as the current best lower bound, and denoted $UB_{k}$ as the current best upper bound, for any $\epsilon$ , and we have that

$\begin{align} UB_{k}-LB_{k} < \epsilon. \end{align}$

(4)

Assume that $(s^{k}, t^{k}, z^{k})$ is a feasible solution of the problem ( $\rm EP_{3}$ ) with that

$s_{i}^{k} = \frac{1}{\sum\limits_{j = 1}^{n}d_{ij}z_{j}^{k}+g_{i}t^{k}}.$

Letting $\upsilon(\rm EP_{3})$ be the global optimal value of the problem ( $\rm EP_{3}$ ), we can get

$\begin{align} \Phi(s^{k}, t^{k},z^{k})-LB_{k} = UB_{k}-LB_{k}\leq \epsilon \end{align}$

(5)

and

$\begin{align} LB_{k}\leq \upsilon(\rm EP_{3}). \end{align}$

(6)

However, $(s^{k}, t^{k}, z^{k})$ is the feasible solution of the problem ( $\rm EP_{3}$ ), and we can follow that

$\begin{align} \Phi(s^{k}, t^{k},z^{k})\geq \upsilon(\rm EP_{3}). \end{align}$

(7)

By the above inequalities (4)–(7), we can get

$\upsilon({\rm EP_{3}})\leq \Phi(s^{k}, t^{k},z^{k}) \leq LB^{k}+\epsilon \leq \upsilon(\rm EP_{3})+\epsilon.$

Therefore, $(s^{k}, t^{k}, z^{k})$ is an $\epsilon$ -global optimum solution of the problem ( $\rm EP_{3}$ ), and

$x^{k} = \frac{z^{k}}{t^{k}}$

is an $\epsilon$ -global optimum solution of the SARP.

If Algorithm 1 fails to terminate within a finite number of iterations, then it will produce an infinite feasible solution sequence $\{x^{k}\}$ of the SARP and an infinite feasible solution sequence $(s^{k}, t^{k}, z^{k})$ of the problem ( $\rm EP_{3}$ ) with

$s_{i}^{k} = \frac{1}{\sum\limits_{j = 1}^{n}d_{ij}z_{j}^{k}+g_{i}t^{k}}.$

Letting $(t^{*}, z^{*})$ be an accumulation point of the sequence $\{(t^{k}, z^{k})\}$ , we can get

$\lim\limits_{k\rightarrow \infty} (t^{k}, z^{k}) = (t^{*},z^{*}).$

By the continuity of the function

$s_{i} = \frac{1}{\sum\limits_{j = 1}^{n}d_{ij}z_{j}+g_{i}t},\ \ i\in\{1,2,\cdots,p-1\},$

we can get that

$\frac{1}{\sum\limits_{j = 1}^{n}d_{ij}z_{j}^{*}+g_{i}t^{*}} = \lim\limits_{k\rightarrow \infty}\frac{1}{\sum\limits_{j = 1}^{n}d_{ij}z_{j}^{k}+g_{i}t^{k}} = \lim\limits_{k\rightarrow \infty}s_{i}^{k} = s_{i}^{*}.$

Thus, $(s^{*}, t^{*}, z^{*})$ is a feasible solution of the problem ( $\rm EP_{3}$ ).

Since $\Big\{LB_{k}\Big\}$ is a monotonic non-decreasing bounded sequence, we get that

$LB_{k} = \Phi^{R}(s^{k}, t^{k}, z^{k})$

and

$LB_{k}\leq \upsilon(\rm EP_{3}),$

and also since $\{UB_{k}\}$ is a non-increasing and bounded sequence, we get that

$UB_{k} = \Phi(s^{k}, t^{k},z^{k})$

and

$UB_{k}\geq \upsilon(\rm EP_{3}).$

So, we have

$LB_{k} = \Phi^{R}(s^{k}, t^{k}, z^{k})\leq \upsilon({\rm EP_{3}})\leq \Phi(s^{k}, t^{k},z^{k}) = UB_{k}.$

Hence, from the termination condition of the algorithm, taking the limit on both side of the above inequalities, we get

$\lim\limits_{k \rightarrow \infty} LB_{k} = \upsilon({\rm EP_{3}}) = \lim\limits_{k \rightarrow \infty} \Phi(s^{k}, t^{k},z^{k}) = \Phi(s^{*}, t^{*},z^{*}) = \lim\limits_{k \rightarrow \infty} UB_{k}.$

Thus, the accumulation point $(s^{*}, t^{*}, z^{*})$ of the sequence ${(s^{k}, t^{k}, z^{k})}$ is a global optimal solution of the problem ( $\rm EP_{3}$ ). At the same time, the accumulation point $x^{*}$ of the sequence $\{x^{k}\}$ with

$x^{k} = \frac{z^{k}}{t^{k}}$

is a global optimal solution of the SARP, and the proof is complete. □

Remark 2. The algorithm proposed in this paper is a rectangular branch-and-bound global optimization algorithm. As is well-known, based on the convergence theory of branch-and-bound global optimization algorithms ^[33], the exhaustiveness of the branching process and the approximation of upper and lower bounds indicate that the proposed rectangular branch-and-bound global optimization algorithm must be convergent.

3.3. Computational complexity of the algorithm

Further, to examine the maximum number of iterations of Algorithm 1, we derive the computational complexity of Algorithm 1. First, we define the size $\Upsilon$ of the rectangle $S$ as

$\Upsilon(S) = \max\{\overline s_{i}-\underline s_{i} \mid i = 1,2,\cdots,p-1\}.$

Theorem 3. Given a termination error $\epsilon > 0$ , if there exists a rectangle $S$ formed by the proposed algorithm at the $k_{th}$ iteration satisfying

$\Upsilon(S) \leq \frac{\epsilon}{(p-1)\omega},$

then we have that

$UB_{k}-LB(S)\leq \epsilon,$

where $LB(S)$ is the optimal value of the ARP over $S$ , and $UB_{k}$ is the currently known best upper bound of the optimum value of the problem ( $\rm EP_{3}$ ).

Proof. Without losing generality, suppose that $(t^{k}, z^{k})$ is the optimal solution of the ARP over $S$ , and let

$s_{i}^{k} = \frac{1}{\sum\limits_{j = 1}^{n}d_{ij}z_{j}^{k}+g_{i}t^{k}},\ \ i = 1,2,\ldots,p-1.$

Then $(s^{k}, t^{k}, z^{k})$ is a feasible solution to the problem ( $\rm EP_{3}$ ). By the method of updating the upper bound and lower bound, and the construction process of the ARP, we have that

$\Phi(s^{k}, t^{k},z^{k})\geq UB^{k}\geq LB(S) = \Phi^{R}(s^{k}, y^{k}, z^{k}).$

By the definition of the size $\Upsilon(S)$ of the rectangle $S$ and

$\Upsilon(S) \leq \frac{\epsilon}{(p-1)\omega},$

it follows that

$\begin{align*} \begin{aligned} UB_{k}-LB(S)\leq& \ \Phi(s^{k}, t^{k}, z^{k})-\Phi^{R}(s^{k}, t^{k},z^{k})\\ = & \ \bigg|\sum\limits_{i = 1}^{p-1}s^{k}_{i}\Big(\sum\limits_{j = 1}^{n}c_{ij}z^{k}_{j}+f_{i}t^{k}\Big)+\sum\limits_{j = 1}^{n}c_{pj}z^{k}_{j}+f_{p}t^{k}\\ & \ -\Big[\sum\limits_{i = 1}^{p-1}\Big(\sum\limits_{j = 1, c_{ij} > 0}^{n}c_{ij}\underline s_{i}z_{j}^{k}+\sum\limits_{j = 1, c_{ij} < 0}^{n}c_{ij}\overline s_{i}^{k}z_{j}^{k} +\sum\limits_{j = 1,f_{i} > 0}^{n}f_{i}\underline s_{i}t^{k}+\sum\limits_{j = 1,f_{i} < 0}^{n}f_{i}\overline s_{i}t^{k}+\sum\limits_{j = 1}^{n}c_{pj}z^{k}_{j}+f_{p}t^{k} \Big)\Big]\bigg|\\ = & \ \bigg|\sum\limits_{i = 1}^{p-1}(s_{i}-\underline s_{i})\sum\limits_{j = 1,c_{ij} > 0}^{n}c_{ij}z_{j}^{k}+\sum\limits_{i = 1}^{p-1}(s_{i}-\overline s_{i})\sum\limits_{j = 1,c_{ij} < 0}^{n}c_{ij}z_{j}^{k} +\sum\limits_{i = 1,f_{i} > 0}^{p-1}(s_{i}-\underline s_{i})f_{i}t^{k}+\sum\limits_{i = 1,f_{i} < 0}^{p-1}(s_{i}-\overline s_{i})f_{i}t^{k}\bigg|\\ \leq& \ \sum\limits_{i = 1}^{p-1}(\overline s_{i}-\underline s_{i})\times\bigg(\sum\limits_{j = 1}^{n}|c_{ij}|z_{j}^{k}+\sum\limits_{i = 1}^{n}|f_{i}|t^{k}\bigg)\\ \leq& \ (p-1)\omega\Upsilon(S)\\ \leq& \ \epsilon.\end{aligned} \end{align*}$

The proof of Theorem 3 is complete.□

Then we can examine the maximum iterations of Algorithm 1, see the following Theorem 4:

Theorem 4. Given the convergent tolerance $\epsilon\in(0, 1)$ , Algorithm 1 can acquire a global optimal solution of the SARP at most

$(p-1)\cdot\left[\log_{2}\frac{(p-1)\omega\Upsilon(S^{0})}{\epsilon}\right]$

iterations.

Proof. In general, we assume that the sub-rectangle $S$ is selected for partitioning in Algorithm 1 at each iteration. After $k\cdot(p-1)$ iterations, we can follow that

$\Upsilon(S)\leq \frac{1}{2^{k}}\Upsilon(S^{0}).$

Based on the former proof of Theorem 3, if

$\frac{1}{2^{k}}\Upsilon(S^{0})\leq \frac{\epsilon}{(p-1)\omega},$

i.e.,

$k\geq \log_{2}\frac{(p-1)\omega\Upsilon(S^{0})}{\epsilon},$

we can follow that

$UB_{k}-LB(S)\leq \epsilon.$

Therefore, after at most

$(p-1)\cdot\left[\log_{2}\frac{(p-1)\omega\Upsilon(S^{0})}{\epsilon}\right]$

iterations, we can get

$\begin{align*} 0&\leq \Phi(s^{k}, t^{k}, z^{k})-\Phi(s^{*}, t^{*}, z^{*})\\&\leq \Phi(s^{k}, t^{k}, z^{k})-LB(S)\\& = UB_{k}-LB(S)\\&\leq \epsilon, \end{align*}$

where $(s^{*}, t^{*}, z^{*})$ is the optimal solution of the problem ( $\rm EP_{3}$ ), and $(s^{k}, t^{k}, z^{k})$ is the best currently know feasible solution for the problem ( $\rm EP_{3}$ ). This implies that $(s^{k}, t^{k}, z^{k})$ is an $\epsilon$ -global optimal solution of the problem ( $\rm EP_{3}$ ) when Algorithm 1 terminates. At the same time, we can follow that $\frac{z^{k}}{t^{k}}$ is an $\epsilon$ -global optimal solution of the SARP, and we complete the proof.□

Remark 3. From the above complexity analysis of the algorithm in Theorem 4, letting

$\Gamma = (p-1)\cdot\left[\log_{2}\frac{(p-1)\omega\Upsilon(S^{0})}{\epsilon}\right],$

the running time of Algorithm 1 is bounded by

$2(\Gamma-1)\times T(m+2p+1, n+1)$

for finding an $\epsilon$ -global optimal solution of the SARP, where $T(m+2p+1, n+1)$ denotes the time taken to solve a linear programming problem with $n+1$ variables and $m+2p+1$ linear constraints.

4. Numerical experiments

In this section, we numerically compare Algorithm 1 with some known extant branch-and-bound algorithms. All tests were implemented in MATLAB R2018a and run on a microcomputer with Intel(R) Core(TM) i5-10400 CPU @ 2.90GHz processor and 8 GB RAM. For all test problems, we provide their computational results. The maximum time limit was set to $10000s$ for all algorithms.

First of all, some small-size certainty examples (see the Appendix Examples 1–12) were tested with Algorithm 1 for comparison with the known extant algorithms ^{[14,21,34,35,36,37,38,39,40]}, and a numerical comparison between some existing algorithms and Algorithm 1 on Examples 1–12 were reported in Table 1 with the given convergence tolerance, where some notations have been used for column headers: Opt. val.: global optimal value; Iter.: number of iterations of the algorithm; Time: the CPU execution time of the algorithm in seconds.

Table 1. Numerical comparison between some existing algorithms and Algorithm 1 on test Examples 1–12.

No.	Algorithms	Opt. val.	Optimal solution	Iter.	Time	$\epsilon$
1	Algorithm 1	-4.83976	(0.1117, 2.3603)	16	0.254	$10^{-2}$
	Benson ^[34]	-4.84151	(0.1000, 2.3750)	4	0.190	$10^{-2}$
	Jiao and Liu ^[39]	-4.84151	(0.1000, 2.3750)	200	4.257	$10^{-2}$
2	Algorithm 1	-2.47143	(1.0000, 0.0000, 0.0000)	11	0.192	$10^{-2}$
	Shen et al. ^[35]	-2.47143	(1.0000, 0.0000, 0.0000)	2	0.015	$10^{-2}$
	Jiao and Liu ^[39]	-2.47124	(1.0001, 0.0000, 0.0001)	54	1.135	$10^{-2}$
3	Algorithm 1	-1.90000	(0.0000, 3.3333, 0.0000)	424	6.907	$10^{-6}$
	Shen and Wang ^[36]	-1.90000	(0.0000, 3.3333, 0.0000)	8	0.926	$10^{-6}$
4	Algorithm 1	1.62318	(0.0000, 0.2841)	39	0.566	$10^{-2}$
	Jiao and Liu ^[39]	1.62319	(0.0000, 0.2861)	93	2.485	$10^{-2}$
5	Algorithm 1	2.86190	(5.0000, 0.0000, 0.0000)	199	2.776	$10^{-3}$
	Jiao and Liu ^[39]	2.86241	(4.8302, 0.0000, 0.0666)	4008	128.0	$10^{-3}$
	Shen and Lu ^[37]	2.86191	(5.0000, 0.0000, 0.0000)	16	0.125	$10^{-3}$
	Gao and Jin ^[38]	2.86190	(5.0000, 0.0000, 0.0000)	12	28.29	$10^{-3}$
6	Algorithm 1	-4.09070	(1.1111, 0.0000, 0.0000)	28	0.359	$10^{-2}$
	Jiao and Liu ^[39]	-4.09062	(1.1106, 0.0000, 0.0015)	619	16.62	$10^{-2}$
	Shen and Lu ^[37]	-4.08741	(1.0715, 0.0000, 0.0000)	17	3.251	$10^{-2}$
7	Algorithm 1	3.71092	(0.0000, 1.6667, 0.0000)	89	1.124	$10^{-4}$
	Jiao and Liu ^[39]	3.71093	(0.0000, 1.6667, 0.0000)	2747	94.64	$10^{-4}$
	Gao and Jin ^[38]	3.7087	(0.0000, 1.6667, 0.0000)	5	4.190	$10^{-4}$
8	Algorithm 1	-3.00225	(0.0000, 2.8455, 0.0000)	36	0.566	$10^{-2}$
	Jiao and Liu ^[39]	-3.00292	(0.0000, 3.3333, 0.0000)	1072	31.746	$10^{-2}$
9	Algorithm 1	4.91267	(1.5015, 1.5024)	30	0.422	$10^{-3}$
	Shen and Lu ^[37]	4.91259	(1.5000, 1.5000)	56	1.087	$10^{-3}$
10	Algorithm 1	-4.09070	(1.1111, 0.0000, 0.0000)	33	0.492	$10^{-2}$
	Jiao et al. ^[40]	-4.09070	(1.1111, 0.0000, 0.0000)	2	0.008	$10^{-6}$
	Jiao and Liu ^[39]	-4.09065	(1.1109, 0.0000, 0.0005)	977	32.41	$10^{-6}$
11	Algorithm 1	3.29167	(3.0000, 4.0000)	138	1.902	$10^{-6}$
	Shen and Wang ^[36]	3.29167	(3.0000, 4.0000)	9	0.489	$10^{-6}$
12	Algorithm 1	4.42857	(5.0000, 0.0000, 0.0000)	67	0.931	$10^{-4}$
	Jiao and Liu ^[39]	4.42794	(4.9930, 0.0000, 0.0000)	128	4.213	$10^{-4}$
	Shi ^[21]	4.42857	(5.0000, 0.0000, 0.0000)	58	2.968	$10^{-4}$

| Show Table

DownLoad: CSV

From the numerical results in Table 1, for Examples 2, 5, 6, 10 and 12, we can follow that Algorithm 1 can obtain the better global optimal solutions and optimal values than the existing algorithms of Jiao and Liu ^[39] and Shen and Lu ^[37]. Algorithm 1 performs better than the method of Jiao and Liu ^[39] for finding the optimal solution in less time and fewer iterations. Therefore, in terms of test Examples 1–12, their experimental results verify that Algorithm 1 is valid and feasible.

Next, we chose two large-scale test problems generated randomly to verify the proposed algorithm further, see Problems 1 and 2 for details. With the given approximation error $\epsilon = 10^{-2}$ , we first tested Problem 1 with large-size variables, numerical comparisons among Algorithm 1, the algorithm of Jiao and Liu ^[39], and the algorithm of Li et al. ^[41], which are reported in Table 2.

Table 2. Numerical comparisons among Algorithm 1, the algorithm of Jiao and Liu ^[39], and the algorithm of Li et al. ^[41] on Problem 1.

$(p, m, n)$	Algorithms	Iter.			Time
$(p, m, n)$	Algorithms	min.	ave.	max.	min.	ave.	max.
(2,100, 1000)	Jiao and Liu ^[39]	34	111.5	342	6.78	22.82	71.53
	Li et al. ^[41]	9	21.8	30	2.21	4.03	5.46
	Algorithm 1	6	14.8	23	1.56	2.73	3.41
(2,100, 3000)	Jiao and Liu ^[39]	55	99.8	159	82.16	147.45	235.12
	Li et al. ^[41]	9	23.4	27	11.26	18.12	24.12
	Algorithm 1	6	12.4	19	11.23	17.89	23.45
(2,100, 5000)	Jiao and Liu ^[39]	41	83.9	152	171.34	339.68	618.89
	Li et al. ^[41]	12	18.1	30	56.56	75.24	96.18
	Algorithm 1	8	12.3	25	38.51	50.45	68.32
(2,100, 7000)	Jiao and Liu ^[39]	49	78.7	124	392.12	634.51	987.42
	Li et al. ^[41]	10	16.9	27	99.84	126.53	185.62
	Algorithm 1	7	11.7	21	68.87	89.45	129.23
(2,100, 10000)	Jiao and Liu ^[39]	13	73.1	129	230.12	1188.43	2145.25
	Li et al. ^[41]	12	18.5	25	241.56	289.25	324.56
	Algorithm 1	8	12.8	17	166.56	204.43	245.52
(3,100, 1000)	Jiao and Liu ^[39]	215	814.4	1756	43.12	175.68	398.53
	Li et al. ^[41]	75	309.4	628	10.89	40.53	72.47
	Algorithm 1	53	238.2	465	7.45	28.54	48.98
(3,100, 3000)	Jiao and Liu ^[39]	*	*	*	*	*	*
	Li et al. ^[41]	92	257.8	378	123.56	254.58	367.92
	Algorithm 1	63	198.8	296	81.47	187.45	284.32
(3,100, 5000)	Jiao and Liu ^[39]	*	*	*	*	*	*
	Li et al. ^[41]	75	273.8	512	278.56	625.48	985.26
	Algorithm 1	54	191.7	348	208.45	452.78	712.45
(3,100, 7000)	Jiao and Liu ^[39]	*	*	*	*	*	*
	Li et al. ^[41]	89	243.5	325	645.38	1201.48	1572.48
	Algorithm 1	61	163.4	242	439.43	805.39	1168.71
(3,100, 10000)	Jiao and Liu ^[39]	*	*	*	*	*	*
	Li et al. ^[41]	130	249.8	426	1580.22	2678.56	4582.58
	Algorithm 1	89	165.2	287	1087.24	1786.13	3090.56
(4,100, 1000)	Jiao and Liu ^[39]	*	*	*	*	*	*
	Li et al. ^[41]	485	3436.6	9856	46.53	323.23	1169.14
	Algorithm 1	317	2332.8	7279	43.62	278.85	985.93

| Show Table

DownLoad: CSV

In and , Avg.Iter denotes the average number of iterations of the algorithm, Avg.Time denotes the average execution CPU time of the algorithm in seconds, " $*$ " denotes the situation that the proposed algorithm failed to terminate in $10000s$ for some of the arbitrary $50$ independently generated test examples. For random Problems 1 and 2, we solved $50$ independently generated test instances and recorded their average results among these $50$ tests, and we highlighted in bold the winner of average results in numerical comparisons.

Table 3. Numerical comparisons between Algorithm 1 and the algorithm of Li et al. ^[41] on Problem 2.

$(p, m, n)$	Algorithms	Iter.			Time
$(p, m, n)$	Algorithms	min.	ave.	max.	min.	ave.	max.
(10,100,300)	Li et al. ^[41]	9	13.6	19	5.28	8.87	12.7
	Algorithm 1	7	9.8	15	4.12	6.45	10.2
(10,100,400)	Li et al. ^[41]	10	16	25	6.90	12.65	20.66
	Algorithm 1	8	12.8	19	5.61	9.68	16.92
(10,100,500)	Li et al. ^[41]	10	17.4	30	8.07	15.89	26.52
	Algorithm 1	9	14.2	26	6.45	12.75	21.45
(15,100,400)	Li et al. ^[41]	50	121.6	201	46.78	118.75	201.66
	Algorithm 1	38	95.6	189	39.98	95.68	179.85
(15,100,500)	Li et al. ^[41]	49	118.1	258	54.57	137.92	303.49
	Algorithm 1	41	98.7	202	41.38	99.56	201.24
(20,100,300)	Li et al. ^[41]	157	321.2	861	126.19	255.46	694.20
	Algorithm 1	118	278.6	598	89.16	202.46	587.45
(20,100,400)	Li et al. ^[41]	99	399.9	1134	99.06	425.77	1199.2
	Algorithm 1	87	312.7	985	87.45	364.10	950.26

| Show Table

DownLoad: CSV

Problem 1. (Li et al. ^[41])

$\begin{eqnarray*} \left\{\begin{array}{l} \min\ \sum\limits_{i = 1}^{p} \frac{\bar{c}^\top_{i}x+\bar{f}_{i}}{\bar{d}^\top_{i}x+\bar{g}_{i}} ,\\[10pt] \mathrm{s.t.}\; \; \; \bar{A}x\leq \bar{b},\\ \; \; \; \; \; \; \,\; x\geq 0, \end{array} \right. \end{eqnarray*}$

where $\bar{c}_{i}\in \mathbb{R}^{n}$ , $\bar{d}_{i}\in \mathbb{R}^{n}$ , $\bar{A}\in \mathbb{R}^{m\times n}$ , $\bar{b}\in \mathbb{R}^{m}$ , $\bar{f}_{i}\in\mathbb{R}, \bar{g}_{i}\in\mathbb{R}, i = 1, 2, \ldots, p$ ; each element of $\bar{c}_{i}$ , $\bar{d}_{i}$ , and $\bar{A}$ is randomly generated from the interval $[0, 10]$ ; each element of $\bar{b}$ is equal to $10$ , and each element of $\bar{f}_{i}$ and $\bar{g}_{i}$ is randomly generated from the interval $[0, 1]$ .

Problem 2. (Li et al. ^[41])

$\begin{eqnarray*} \left\{\begin{array}{l} \min\ \ \sum\limits_{i = 1}^{p} \frac{\sum\limits_{j = 1}^{n}\tilde{\gamma}_{ij}x_{j}+\tilde{\xi}_{i}}{\sum\limits_{j = 1}^{n}\tilde{\delta}_{ij}x_{j}+\tilde{\eta}_{i}}, \\[10pt] \mathrm{s.t.}\; \; \;\; \tilde{A}x\leq \tilde{b},\ \ x\geq 0, \end{array} \right. \end{eqnarray*}$

where $\tilde{\gamma}_{ij}, \tilde{\xi}_{i}, \tilde{\delta}_{ij}, \tilde{\eta}_{i}\in \mathbb{R}$ , $i = 1, 2, \ldots, p, j = 1, 2, \ldots, n; \; \tilde{A}\in \mathbb{R}^{m\times n}$ , $\tilde{b}\in \mathbb{R}^{m}$ ; all $\tilde{\gamma}_{ij}$ and $\tilde{\delta}_{ij}$ are randomly generated from $[-0.1, 0.1]$ ; all elements of $\tilde{A}$ are randomly generated from $[0.01, 1]$ ; all elements of $\tilde{b}$ are equal to $10$ ; and all $\tilde{\xi}_{i}$ and $\tilde{\eta}_{i}$ satisfy

$\sum\limits_{j = 1}^{n}\tilde{\gamma}_{ij}x_{j}+\tilde{\xi}_{i} > 0$

and

$\sum\limits_{j = 1}^{n}\tilde{\delta}_{ij}x_{j}+\tilde{\eta}_{i} > 0.$

From the results in , for Problem 1 with the large-size number of variables, we first get the observation that the algorithm proposed in Jiao and Liu ^[39] is more time-consuming than Algorithm 1. Especially, when $p = 3$ , $m = 100, \; n = 3000$ ; $p = 3$ , $m = 100, \; n = 5000$ ; $p = 3$ , $m = 100, \; n = 7000$ ; $p = 3$ , $m = 100, \; n = 10000$ ; $p = 4$ , $m = 100, \; n = 1000$ ; the algorithm of Jiao & Liu ^[39] failed to solve all $50$ independently generated instances in $10000s$ , but Algorithm 1 can obtain the global optimal solution of test Problem 1 with higher computational efficiency. Second, the computational efficiency of Algorithm 1 is superior to the algorithm of Li et al. ^[41] in all cases.

From the numerical comparisons for Problem 2 in Table 3, the computational efficiency of Algorithm 1 is superior to the algorithm of Li et al. ^[41] in all cases.

From the numerical comparisons in Tables 1–3, we can get that Algorithm 1 can globally solve the sum of affine ratios problem to obtain their global optimal solutions and optimal values with higher computational efficiency.

5. Conclusions

This paper studies the sum of affine ratios problem and presents an outcome space branch-and-bound algorithm. In this algorithm, we proposed a novel linearization technique for constructing the affine relaxation problem of the equivalent problem. Moreover, the computational complexity of the algorithm is analyzed, and the maximum number of iterations of the algorithm is derived. Algorithm 1 can find an $\epsilon$ -global optimal solution in at most

$(p-1)\cdot\left[\log_{2}\frac{(p-1)\omega\Upsilon(S^{0})}{\epsilon}\right]$

iterations. Numerical comparisons show the effectiveness and superiority of Algorithm 1. Future work will extend Algorithm 1 to solve the sum of nonlinear ratios problem.

Author contributions

Yan Shi: formal analysis, investigation, resources, methodology, writing-original draft, validation, and data curation; Qunzhen Zheng: formal analysis, invesigation, writing-review & editing, software, data curation, conceptualization, supervision, project administration; Jingben Yin: project administration, methodology, validation, and formal funding acquisition. All authors have read and agreed to the published version of the manuscript.

Use of AI tools declaration

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

Acknowledgments

This paper is supported by the Key Scientific and Technological Research Projects in Henan Province (202102210147, 192102210114).

Conflict of interest

The authors declare no conflicts of interest.

Appendix

Test Examples 1–12 are given as follows:

Example 1. (Benson ^[34])

$\begin{eqnarray*} \ \ \left\{\begin{array}{ll} \min &f(x) = \frac{-3.333x_1-3x_2-1}{1.666x_1+x_2+1}+\frac{-4x_1-3x_2-1}{x_1+x_2+1},\\ {\text{s.t. }}\ & 5x_1+4x_2\leq 10,\\ & -x_1\leq -0.1, \\ & -x_2\leq -0.1, \\ & -2x_1-x_2\leq -2, \\ & x_1, x_2\geq 0. \end{array} \right. \end{eqnarray*}$

Example 2. (Phuong and Tuy ^[14] and Shen et al. ^[35])

$\begin{eqnarray*} \ \ \left\{\begin{array}{ll} \max &\frac{3x_1+x_2-2x_3+0.8}{2x_1-x_2+x_3}+\frac{4x_1-2x_2+x_3}{7x_1+3x_2-x_3},\\ {\text{s.t. }}\ &x_1+x_2-x_3\leq 1,\\ & -x_1+x_2-x_3\leq -1,\\ &12x_1+5x_2+12x_3\leq 34.8,\\ &12x_1+12x_2+7x_3\leq 29.1,\\ &-6x_1+x_2+x_3\leq- 4.1.\\ \end{array} \right. \end{eqnarray*}$

Example 3. (Shen et al. ^[35], Shen and Wang ^[36])

$\begin{eqnarray*} \ \ \left\{\begin{array}{ll} \max &\frac{3x_1+4x_2+50}{3x_1+5x_2+4x_3+50}-\frac{3x_1+5x_2+3x_3+50}{5x_1+5x_2+4x_3+50}- \frac{x_1+2x_2+4x_3+50}{5x_2+4x_3+50}-\frac{4x_1+3x_2+3x_3+50}{3x_2+3x_3+50},\\ {\text{s.t. }}\ &6x_1+3x_2+3x_3\leq10,\\ & 10x_1+3x_2+8x_3\leq10,\\ & x_1,x_2,x_3\geq0. \end{array} \right. \end{eqnarray*}$

Example 4. (Shen et al. ^[35])

$\begin{eqnarray*} \ \ \left\{\begin{array}{ll} \text{min} & \frac{-x_{1}+2x_{2}+2}{3x_{1}-4x_{2}+5}+\frac{4x_{1}-3x_{2}+4}{-2x_{1}+x_{2}+3},\\ \text{s . t . }& x_{1}+x_{2}\leq 1.5,\\ & x_{1}-x_{2}\leq 0 ,\\ & 0\leq x_{1}\leq 1, 0\leq x_{2}\leq 1. \end{array} \right. \end{eqnarray*}$

Example 5. (Shen and Lu ^[36], Gao and Jin ^[38])

$\begin{eqnarray*} \ \ \left\{\begin{array}{ll} \text{min} & \frac{3x_{1}+5x_{2}+3x_{3}+50}{3x_{1}+4x_{2}+5x_{3}+50} +\frac{3x_{1}+4x_{2}+50}{4x_{1}+3x_{2}+2x_{3}+50} +\frac{4x_{1}+2x_{2}+4x_{3}+50}{5x_{1}+4x_{2}+3x_{3}+50},\\ \text{s . t . }& 2x_{1}+x_{2}+5x_{3}\leq 10, \\ & x_{1}+6x_{2}+2x_{3}\leq 10,\\ & 9x_{1}+7x_{2}+3x_{3}\geq 10,\\ & x_{1},x_{2},x_{3}\geq 0. \end{array} \right. \end{eqnarray*}$

Example 6. (Shen and Lu ^[37])

$\begin{eqnarray*} \ \ \left\{\begin{array}{ll} \text{max} & \frac{4x_{1}+3x_{2}+3x_{3}+50}{3x_{2}+3x_{3}+50} +\frac{3x_{1}+4x_{3}+50}{4x_{1}+4x_{2}+5x_{3}+50} +\frac{x_{1}+2x_{2}+5x_{3}+50}{x_{1}+5x_{2}+5x_{3}+50} +\frac{x_{1}+2x_{2}+4x_{3}+50}{5x_{2}+4x_{3}+50},\\ \text{s . t . }& 2x_{1}+x_{2}+5x_{3}\leq 10,\\ & x_{1}+6x_{2}+3x_{3}\leq 10,\\ & 5x_{1}+9x_{2}+2x_{3}\leq 10,\\ & 9x_{1}+7x_{2}+3x_{3}\leq 10,\\ & x_{1},x_{2},x_{3}\geq 0. \end{array} \right. \end{eqnarray*}$

Example 7. (Shen and Lu ^[37], Gao and Jin ^[38])

$\begin{eqnarray*} \ \ \left\{\begin{array}{ll} \text{min} & \frac{4x_{1}+3x_{2}+3x_{3}+50}{3x_{2}+3x_{3}+50} +\frac{3x_{1}+4x_{3}+50}{4x_{1}+4x_{2}+5x_{3}+50} +\frac{x_{1}+2x_{2}+4x_{3}+50}{x_{1}+5x_{2}+5x_{3}+50} +\frac{x_{1}+2x_{2}+4x_{3}+50}{5x_{2}+4x_{3}+50},\\ \text{s . t . }& 2x_{1}+x_{2}+5x_{3}\leq 10,\\ & x_{1}+6x_{2}+3x_{3}\leq 10,\\ & 9x_{1}+7x_{2}+3x_{3}\geq 10,\\ & x_{1},x_{2},x_{3}\geq 0. \end{array} \right. \end{eqnarray*}$

Example 8. (Shen and Lu ^[37])

$\begin{eqnarray*} \ \ \left\{\begin{array}{ll} \text{max} & \frac{3x_{1}+5x_{2}+3x_{3}+50}{3x_{1}+4x_{2}+5x_{3}+50} +\frac{3x_{1}+4x_{2}+50}{4x_{1}+3x_{2}+2x_{3}+50} +\frac{4x_{1}+2x_{2}+4x_{3}+50}{5x_{1}+4x_{2}+3x_{3}+50},\\ \text{s . t . }& 6x_{1}+3x_{2}+3x_{3}\leq 10,\\ & 10x_{1}+3x_{2}+8x_{3}\leq 10,\\ & x_{1},x_{2},x_{3}\geq 0. \end{array} \right. \end{eqnarray*}$

Example 9. (Shen and Lu ^[37], Gao and Jin ^[38])

$\begin{eqnarray*} \ \ \left\{\begin{array}{ll} \text{min} & \frac{37x_{1}+73x_{2}+13}{13x_{1}+13x_{2}+13}+\frac{63x_{1}-18x_{2}+39}{13x_{1}+26x_{2}+13},\\ \text{s . t . }& 5x_{1}-3x_{2} = 3,\\ & 1.5\leq x_{1}\leq 3. \end{array} \right. \end{eqnarray*}$

Example 10. (Jiao and Liu ^[39], Jiao et al. ^[40], Shen Wang ^[36])

$\begin{eqnarray*} \ \ \left\{\begin{array}{ll} \text{max} & \frac{4x_{1}+3x_{2}+3x_{3}+50}{3x_{2}+2x_{3}+50} +\frac{3x_{1}+4x_{2}+50}{4x_{1}+4x_{2}+5x_{3}+50} +\frac{x_{1}+2x_{2}+5x_{3}+50}{x_{1}+5x_{2}+5x_{3}+50}+\frac{x_{1}+2x_{2}+4x_{3}+50}{5x_{2}+4x_{3}+50},\\ \text{s . t . }& 2x_{1}+x_{2}+5x_{3}\leq 10, \\ & x_{1}+6x_{2}+3x_{3}\leq 10,\\ & 5x_{1}+9x_{2}+2x_{3}\leq 10,\\ & 9x_{1}+7x_{2}+3x_{3}\leq 10,\\ & x_{1},x_{2},x_{3}\geq 0. \end{array} \right. \end{eqnarray*}$

Example 11. (Shen and Wang ^[36], Shi ^[21])

$\begin{eqnarray*} \ \ \left\{\begin{array}{ll} \text{max} & \frac{37x_{1}+73x_{2}+13}{13x_{1}+13x_{2}+13} +\frac{63x_{1}-18x_{2}+39}{-13x_{1}-26x_{2}-13} +\frac{13x_{1}+13x_{2}+13}{63x_{1}-18x_{2}+39} +\frac{13x_{1}+26x_{2}+13}{-37x_{2}-73x_{3}-13},\\ \text{s . t . }& 5x_{1}-3x_{2} = 3, \\ & 1.5\leq x_{1}\leq 3. \end{array} \right. \end{eqnarray*}$

Example 12. (Shi ^[21])

$\begin{eqnarray*} \ \ \left\{\begin{array}{ll} \text{max} & \frac{4x_{1}+3x_{2}+3x_{3}+50}{3x_{2}+3x_{3}+50} +\frac{3x_{1}+4x_{3}+50}{4x_{1}+4x_{2}+5x_{3}+50} +\frac{x_{1}+2x_{2}+5x_{3}+50}{x_{1}+5x_{2}+5x_{3}+50} +\frac{x_{1}+2x_{2}+4x_{3}+50}{5x_{2}+4x_{3}+50},\\ \text{s . t . }& 2x_{1}+x_{2}+5x_{3}\leq 10, \\ & x_{1}+6x_{2}+2x_{3}\leq 10,\\ & 9x_{1}+7x_{2}+3x_{3}\geq 10,\\ & x_{1},x_{2},x_{3}\geq 0. \end{array} \right. \end{eqnarray*}$

References

[1]	Road traffic safety (2017) In Wikipedia, The Free Encyclopedia. Available from: https://en.wikipedia.org/w/index.php?title=Road_traffic_safety&oldid=783832588
[2]	Vehicle safety communications project final report HS-810-591. US Department of Transortation National Highway Traffic Safety Administration, Washington, DC, USA, 2006, pp. 1-10.
[3]	IEEE Standard 802.11p: IEEE standard for information technology telecommunications and information exchange between systems local and metropolitan area networks specific requirements; Part 11: Wireless LAN medium access control (MAC) and physical layer (PHY) specifications; Amendment 6: Wireless access in vehicular environments, 2010.
[4]	Cailean AM, Cagneau B, Chassagne L, et al. (2014) A survey on the usage of DSCR and VLC in communication-based vehicle safety applications. Proceedings of the 21st IEEE Symposium on Communications and Vehicular Technology in the Benelux (SCVT), 69-74
[5]	Abuelsamid S (2016) New cars could be required to talk to each other as soon as 2020. Retrieved from https://www.forbes.com/sites/samabuelsamid/2016/12/13/nhtsa-finally-issues-draft-v2v-communications-rule-could-be-mandatory-from-2021
[6]	Farquhar P (2016) There's one major obstacle to a driverless car future that tech can't solve -- and that's you. Retrieved from https://www.businessinsider.com.au/theres-one-major-obstacle-to-a-driverless-car-future-that-tech-cant-solve-and-thats-you-2016-12
[7]	Nellore K, Hancke GP (2016) A survey on urban traffic management system using wireless sensor networks. Sensors 16: 1-25.
[8]	Zhao J, Cao G (2008) VADD: Vehicle-assisted data delivery in vehicular ad hoc networks. IEEE T Veh Technol 57: 1910-1922.
[9]	Skordylis A, Trigoni N (2008) Delay-bounded routing in vehicular ad-hoc networks'. Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing, 341-350.
[10]	Ding Y, Wang C, Xiao L (2007) A static-node assisted adaptive routing protocol in vehicular networks. Proceedings of the 4th ACM Workshop on Vehicular Ad Hoc Networks, 59-68.
[11]	Jeong J, Guo S, Gu Y, et al. (2009) TBD: Trajectory-based data forwarding for light-traffic vehicular networks. Proceedings of the 29th IEEE International Conference on Distributed Computing Systems, 231-238.
[12]	Jeong J, Guo S, Gu Y, et al. (2010) TSF: Trajectory-based statistical forwarding for infrastructure-to-vehicle data delivery in vehicular networks. Proceedins of the 30th IEEE International Conference on Distributed Computing Systems, 557-566.
[13]	Kenney JB (2011) Dedicated short-range communications (DSRC) standards in the united states. P IEEE 99: 1162-1182.
[14]	Camp T, Boleng J, Davies V (2002) A survey of mobility models for ad hoc network research. Wireless Communications and Mobile Computing 2: 483-502.
[15]	Carter A (2005) The status of vehicle-to-vehicle communication as a means of improving crash prevention performance. Tech. Rep. 05-0264.
[16]	Eze EC, Zhang S, Liu E (2014) Vehicular ad hoc networks (VANETs): Current state, challenges, potentials and way forward. Proceedings of the 20th International Conference on Automation and Computing, 176-181.
[17]	Máttyus G, Luo W, Urtasun R (2017) DeepRoadMapper: Extracting road topology from aerial images. Proceedings of the 2017 IEEE International Conference on Computer Vision, 3458-3466.
[18]	Wu H, Fujimoto R, Guensler R, et al. (2004) MDDV: A mobility-centric data dissemination algorithm for vehicular networks. Proceedings of the 1st ACM International Workshop on Vehicle Ad Hoc Network, 47-56.
[19]	Khan F, Nguang SK (2020) Location-based data delivery between vehicles and infrastructure. IET Intell Transp Sy 14: 288-296.
[20]	Khan F, Nguang SK (2017) LRF: Location-based reverse forwarding for infrastructure-to-vehicle data delivery. Proceedings of the 9th International Conference on Signal Processing Systems, 32-36.
[21]	Li Y, Shi X, Lindgren A, et al. (2018) Context-aware data dissemination for ICN-based vehicular ad hoc networks. Information 9: 263.
[22]	Zhang L, Afanasyev A, Burke J, et al. (2014) Named Data Networking. ACM SIGCOMM Comput Commun Rev 44: 66-73.
[23]	Xu Y, Tong S, Zhang T, et al. (2020) Compass: Directing named data transmission in VANETs by dynamic directional interfaces. IEEE Access 8: 8418-8435.
[24]	Ahed K, Benamar M, Lahcen AA, et al. (2020) Forwarding strategies in vehicular named data networks: A survey. Journal of King Saud University - Computer and Information Sciences.
[25]	Boukerche A, Coutinho R (2019) LoIcen: A novel location-based and information-centric architecture for content distribution in vehicular networks. Ad Hoc Networks 93: 101899.
[26]	Boukerche A, Coutinho R, Yu X (2017) LISIC: A link stability based protocol for vehicular information-centric networks. IEEE 14th International Conference on Mobile Ad Hoc and Sensor Systems (MASS), 233-240.
[27]	Coutinho R, Boukerche A, Yu X (2018) A novel location-based content distribution protocol for vehicular named-data networks. IEEE Symposium on Computers and Communications (ISCC), 01007-01012.
[28]	Sousa M, Arajo FR, Sampaio L (2018) A link-stability based interest-forwarding strategy for vehicular named data networks. IEEE Internet Comput 22: 16-26.

Reader Comments

Your name:*

Email:*
© 2021 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)