1. Introduction

Multilevel programming deals with decision-making situations in which decision makers are arranged within a hierarchical structure. Trilevel programming, the case of multilevel programming containing three planner, occurs in a variety of applications such as planning ^[6,7], security and accident management ^[1,18], supply chain management ^[14,17], economics, ^[10] and decentralized inventory ^[9]. In a trilevel decision-making process, the first-level planner (leader), in attempting to optimize his objective function, chooses values for the variables that he controls. Next, the second-level planner in attempting to optimize his objective function while considering the reactions of the third-level planner chooses values for the variables that he controls. Lastly, the third-level planner, with regard to the decisions made by the previous levels, optimizes his own objective function. A number of researchers have studied the linear trilevel programming (LTLP) problem, and have proposed some procedures to solve it. Some algorithms are proposed based on penalty method ^[16], Kuhn-Tucker transformation ^[2], multi-parametric approach ^[5], and enumerating extreme points of constraint region ^[19] to find the exact optimal solution to special classes of trilevel programming problem. In addition, because of the complexity of solving trilevel problems especially for large-scale problems, some other researches attempted to use fuzzy ^[13] and meta-heuristic approaches ^[8,15] to find good approximate solutions for these problems. For a good bibliography of the solution approaches to solve trilevel programming problems, the interested reader can refer to ^[11].

The present study investigates the trilevel Kth-best algorithm offered by Zhang et. al. ^[19] at a higher level of accuracy. First, some of the geometric properties of the feasible region of the LTLP problem have been stated and proven. It ought to be mentioned that despite the similarity of some presented theoretical results in this paper with Ref. ^[19], the techniques of the proof are different. Then, a modified version of the trilevel Kth-Best algorithm has been proposed regarding unboundedness of objective functions in both the second level and third level which is not considered in the proposed Kth-Best algorithm in reference ^[19]. Moreover, it is shown that the amount of computations in the solving process by the modified trilevel Kth-Best algorithm is less than of that of the solving process by the traditional trilevel Kth-Best algorithm. In addition, in case of finding the optimal solution of linear trilevel programming problems with conflicting objective functions, the modified Kth-Best algorithm is capable of giving more accurate solutions.

The organization of the paper is as follows. Basic definitions concerning LTLP problem that we shall investigate, are presented in Section 2. Some theoretical and geometric properties of the LTLP problem are studied in Section 3. Based on the facts stated in Section 3, a modified trilevel Kth-Best algorithm is proposed to solve the LTLP problem in Section 4. To show the superiority of the proposed algorithm over the traditional Kth-Best algorithm, some numerical examples are presented in Section 5. Ultimately, the paper is concluded with Section 6.

---

2. Basic definitions of linear trilevel programming problem

As it is mentioned before, we consider the linear trilevel programming problem which can be formulated as follows:

$\begin{align} \label{prob1} &\min\limits_{x_1 \in X_1} \qquad f_1(x_1, x_2, x_3) = \sum\limits_{j = 1}^3 \alpha_{1j}^T x_j \nonumber \\ &\qquad s.t \qquad \sum\limits_{j = 1}^3 A_{1j} x_j \le b_1 \qquad \text{where $x_2, x_3$ solve:} \nonumber \\ &\qquad \qquad \min\limits_{x_2 \in X_2} \qquad f_2(x_1, x_2, x_3) = \sum\limits_{j = 1}^3 \alpha_{2j}^T x_j \nonumber \\ &\qquad \qquad \qquad s.t \qquad \sum\limits_{j = 1}^3 A_{2j} x_j \le b_2 \qquad \text{where $x_3$ solves:}\nonumber \\ &\qquad \quad \qquad \qquad \min\limits_{x_3 \in X_3} \qquad f_3(x_1, x_2, x_3) = \sum\limits_{j = 1}^3 \alpha_{3j}^T x_j \\ &\qquad \quad \qquad \qquad \qquad s.t \qquad \sum\limits_{j = 1}^3 A_{3j} x_j \le b_3 \nonumber % &\qquad \quad \qquad \qquad \qquad \qquad x_j \geq 0 \qquad j = 1, 2, 3 \nonumber \end{align}$

(2.1)

where $x_i \in X_i$, $X_i$ is an indiscrete subset of $\bf{R}^{n_i}_+$ for $i = 1, 2, 3$ and $\alpha_{ij}, A_{ij} , b_i$ are vectors and matrices of conformal dimensions.

In this section, we state some definitions and notations about the LTLP problem.

● Constraint region:

$S = \{ (x_1, x_2, x_3) \in X_1 \times X_2 \times X_3: \sum_{j = 1}^3 A_{ij} x_j \le b_i , \ \ i = 1, 2, 3 \}.$

● Constraint region for middle and bottom level, for fixed $\bar{x}_1$:

$S_2(\bar{x}_1) = \{ (x_2, x_3) \in X_2 \times X_3 : \sum_{j = 2}^3 A_{ij} x_j \le b_i - A_{i1}\bar{x}_1 , \ \ i = 2, 3 \}.$

● Feasible set for the level 3, for fixed $(\bar{x}_1, \bar{x}_2)$ :

$\Omega_3( \bar{x}_1, \bar{x}_2) = \{ x_3 \in X_3 : A_{33} x_3 \le b_3 - \sum_{j = 1}^{2} A_{3j}\bar{x}_j \}.$

● Rational reaction set for level 3, for fixed $(\bar{x}_1, \bar{x}_2)$ :

$\Psi_3 ( \bar{x}_1, \bar{x}_2) = argmin \{ f_3(\bar{x}_1, \bar{x}_2, x_3) : x_3 \in \Omega_3(\bar{x}_1, \bar{x}_2) \}$.

● Feasible set for level 2, for fixed $\bar{x}_1$:

$\Omega_2( \bar{x}_1) = \{ (x_2, x_3) \in S_2(\bar{x}_1) : x_3 \in \Psi_3(\bar{x}_1, x_2) \}.$

● Rational reaction set for level 2, for fixed $\bar{x}_1$:

$\Psi_{2} ( \bar{x}_1) = argmin \{ f_{2}(\bar{x}_1, x_2, x_3) : (x_2, x_3) \in \Omega_2(\bar{x}_1) \}.$

● Inducible region :

$IR = \{ (x_1, x_2, x_3) \in S : (x_2, x_3) \in \Psi_2(x_1) \}.$

In the above definitions, the term $argmin \{ f(x): x \in S \}$ denotes the set of all minimizers of the function $f$ over the set $S$. Now we can express the definition of the feasible solution and optimal solution to the LTLP problem as follows:

Definition 2.1. A point $(x_1, x_2, x_3)$ is said to be feasible solution to the LTLP problem (2.1) if $(x_1, x_2, x_3) \in IR$.

Definition 2.2. A feasible point $(x_1^*, x_2^*, x_3^*)$ is said to be optimal solution to the LTLP problem (2.1) if $f_1(x_1^*, x_2^*, x_3^*) \le f_1(x_1, x_2, x_3),$ for all $(x_1, x_3, x_3) \in IR.$

In view of the above Definitions, determining the solution for the LTLP problem (2.1) is equal to solve the following problem:

$\begin{equation} \label{origin} \min \{f_1(x_1, x_2, x_3) : (x_1, x_2, x_3) \in IR\}. \end{equation}$

(2.2)

---

3. Theoretical properties

In this section, we will demonstrate some geometric properties of the problem (2.1). Let $F_1, ..., F_r$, denote the non-empty faces of $S$. We will denote by $S_{X_i}$ and $S_{X_i \times X_j}$ the projection of $S$ onto $X_i$ and $X_i \times X_j$ respectively, for $1 \le i, j \le 3$. We will also use the following assumptions to come up with the existence of an optimal solution.

Assumption 3.1. $S$ is a non-empty and compact polyhedron.

Assumption 3.2. $\Psi_2(x_1)$ and $\Psi_3(x_1, x_2)$, are non-empty and single-valued for all $x_1 \in S_{X_1}$ and $(x_1, x_2) \in S_{X_1 \times X_2}$ respectively.

Assumption 3.3. $\Psi_2(.)$ is continuous on $S_{X_1}$.

Note that by Assumption 3.1, we can conclude that $S_{X_i}$, and $S_{X_i \times X_j}$, for $i, j \in \{ 1, 2, 3 \},$ and $F_k$ for $\ k \in \{1, ..., r\}$ are also non-empty compact polyhedrons. The following example demonstrates that Assumption 3.3 is necessary for existence an optimal solution to the LTLP problem.

Example 3.1.

$\begin{align*} &\max\limits_{x_1} \quad x_1+10x_2-2x_3+x_4 \\ &\quad s.t \quad 0 \le x_1 \le 1 \\ &\qquad \qquad \max\limits_{x_2, x_3} \quad x_2+2x_3 \\ &\qquad \qquad \quad s.t \quad x_2+x_3 \le x_1 \\ &\qquad \qquad \qquad 0 \le x_2, x_3 \le 1 \\ &\qquad \qquad \qquad x_4 = 0 \\ &\qquad \qquad \qquad \qquad \max\limits_{x_4} \quad x_4 \\ &\qquad \qquad \qquad \qquad s.t \quad x_4 \le x_3 \\ &\qquad \qquad \qquad \qquad \qquad x_4 \le 1- x_3 \end{align*}$

In this example, we have

$\begin{equation*} \Psi_3(x_1, x_2, x_3) = \left \{ \begin{array}{lll} x_3&\ \ \text{if}&\ \ 0 \le x_3\le \frac{1}{2}, \\ && \\ 1-x_3&\ \ \text{if}&\ \frac{1}{2} \le x_3 \le 1. \end{array} \right. \end{equation*}$

Then,

$\Omega_2(x_1) = \{ (x_2, x_3, x_4): x_2+x_3 \le x_1 , 0 \le x_2 \le 1 , 0 \le x_3 \le \frac{1}{2} , x_4 = x_3 = 0 \} \cup$

$\{ (x_2, x_3, x_4): x_2+x_3 \le x_1 , 0 \le x_2 \le 1 , \frac{1}{2}\le x_3 \le 1 , x_4 = 1-x_3 = 0 \},$

and

$\begin{equation} \label{discon2} \Psi_2(x_1) = argmax \{ x_2+2x_3: (x_2, x_3, x_4) \in \Omega_2(x_1) \} \end{equation}$

(3.1)

It is clear that if $0 \le x_1 < 1$, the optimal solution of the problem (3.1) is $(x_1, 0, 0),$ and if $x_1 = 1$, the optimal solution is $(0, 1, 0)$. Therefore,

$\begin{equation*} \Psi_2(x_1) = \left \{ \begin{array}{lll} (x_1, 0, 0)&\ \ \text{if}& 0 \le x_1 < 1 \\ &&\\ (0, 1, 0)&\ \ \text{if}& x_1 = 1 \end{array} \right. \end{equation*}$

It is evident that $\Psi_2$ is discontinuous at $x_1 = 1$. Although, in this problem, the first level objective function has the supremum value equal to $11$ when we approach the point $(1, 1, 0, 0)$, but the problem does not have an optimal solution.

Lemma 3.1. Let $N = \{ (\bar{x}_1, x_2, x_3) : (x_2, x_3) \in S_2(\bar{x}_1) \}$ and $(\bar{x}_1, \bar{x}_2, \bar{x}_3) \in {ri} \ F \cap IR$ where $F$ is a non-empty face of $S$, then $F \cap N = \{(\bar{x}_1, \bar{x}_2, \bar{x}_3) \}$. The term ${ri} \ F$ denotes the relative interior of $F$.

Proof. It follows from $(\bar{x}_1, \bar{x}_2, \bar{x}_3)\in IR$ that $(\bar{x}_2, \bar{x}_3) \in \Psi_2(\bar{x}_1)$. Moreover, $\Psi_2(\bar{x}_1)$ is nonempty and single-valued. Therefore, $(\bar{x}_2, \bar{x}_3)$ is the unique optimal solution of the following linear bilevel programming problem:

$\begin{align} \label{prob2} &\qquad \qquad \min\limits_{x_2 \geq 0} \qquad \sum\limits_{j = 2}^3 \alpha_{2j}^T x_j \nonumber \\ &\qquad \qquad \qquad s.t \qquad \sum\limits_{j = 2}^3 A_{2j} x_j \le b_2 -A_{21}\bar{x}_1 \qquad \text{where $x_3$ solves:}\nonumber \\ &\qquad \quad \qquad \qquad \min\limits_{x_3 \geq0} \qquad \sum\limits_{j = 2}^3 \alpha_{3j}^T x_j \\ &\qquad \quad \qquad \qquad \qquad s.t \qquad \sum\limits_{j = 2}^3 A_{3j} x_j \le b_3 -A_{31}\bar{x}_1 \nonumber % &\qquad \quad \qquad \qquad \qquad \qquad x_j \geq 0 \qquad j = 2, 3 \nonumber \end{align}$

(3.2)

By Theorem 5.2.2 of ^[3] we conclude that $(\bar{x}_2, \bar{x}_3)$ is an extreme point of $S_2(\bar{x}_1)$. Now let $(\tilde{x}_2, \tilde{x}_3)$ be another point of the $S_2(\bar{x}_1)$ and $(\bar{x}_1, \tilde{x}_2 , \tilde{x}_3)$ belongs to $F \cap N$.

Since $(\bar{x}_1, \bar{x}_2, \bar{x}_3) \in {ri} \ F$ and $(\bar{x}_1, \tilde{x}_2, \tilde{x}_3) \in F$, there exists a $\gamma > 1$ such that

$(\bar{x}_1, \hat{x}_2, \hat{x}_3) = \gamma (\bar{x}_1, \bar{x}_2, \bar{x}_3)+(1-\gamma ) (\bar{x}_1, \tilde{x}_2, \tilde{x}_3) \in F$ (Theorem 6.4 of ^[12]). If we set $\beta = \dfrac{\gamma -1}{\gamma}$, then, $0 < \beta < 1$ and $(\bar{x}_1, \bar{x}_2, \bar{x}_3)$ can be written as:

$(\bar{x}_1, \bar{x}_2, \bar{x}_3) = \beta (\bar{x}_1, \tilde{x}_2, \tilde{x}_3 ) +( 1- \beta)(\bar{x}_1, \hat{x}_2, \hat{x}_3)$.

Thus, it can be concluded that $(\bar{x}_2, \bar{x}_3) = \beta (\tilde{x}_2, \tilde{x}_3)+(1- \beta)(\hat{x}_2, \hat{x}_3)$. In addition, it can be clearly seen that $(\tilde{x}_2, \tilde{x}_3)$ and $(\hat{x}_2, \hat{x}_3)$ are belong to $S_2(\bar{x}_1)$, which contradicts the fact that $(\bar{x}_2, \bar{x}_3)$ is an extreme point of $S_2(\bar{x}_1)$. This completes the proof.

Corollary 3.1. Let $\bar{N} = \{ (\bar{x}_1, x_2, x_3) : (\bar{x}_1, x_2, x_3) \in S \}$ and $(\bar{x}_1, \bar{x}_2, \bar{x}_3) \in {ri} \ F\cap IR$ where $F$ is a non-empty face of $S$ . Then $F \cap \bar{N} = \{(\bar{x}_1, \bar{x}_2, \bar{x}_3) \}.$

Proof. The statement is immediately derived from the fact that

$\ \bar{N} \subset \{(\bar{x}_1, x_2, x_3): (x_2, x_3)\in S_2(\bar{x}_1) \}$

Theorem 3.1. Let $IR \cap {ri} \ F \neq \emptyset$ where $F$ is a non-empty face of S. Then, $F\subset IR$.

Proof. Let $(\hat{x}_1, \hat{x}_2, \hat{x}_3) \in IR \cap {ri} \ F$ and let $(\bar{x}_1 , \bar{x}_2, \bar{x}_3) \in F$ be arbitrary. Since $(\hat{x}_1, \hat{x}_2, \hat{x}_3) \in {ri} \ F$, we can find a neighborhood $\hat{N}$ around it such that

$N = \hat{N} \cap {aff} \ F \subset {ri} \ F$, where ${aff} \ F$ denotes the affine hull of face $F$. Since $\Psi_2$ is a single-valued and continuous map over $S_{X_1}$, we can find a neighborhood $W$ around $\hat{x}$ such that:

$\{ (x, \Psi_2(x)):\ x \in W \} \subset N \subset {ri} \ F.$

Moreover, we can choose $0 < \gamma_1 < 1$ such that

$B = \{x_1 \in S_{X_1} : x_1 = \gamma \bar{x}_1+(1- \gamma)\hat{x}_1, \ 0\le \gamma \le \gamma_1 \} \subset W$. Then,

$\{ (x_1, \Psi_2( x_1)) :x_1 \in B \} \subset N \subset {ri} \ F$.

Besides, for all $\beta \in [0, 1)$,

$\beta (\bar{x}_1, \bar{x}_2, \bar{x}_3)+ (1- \beta)(\hat{x}_1, \hat{x}_2, \hat{x}_3) \in {ri} \ F$, (see Ref. ^[12], Theorem 6.1).

Consequently, from Corollary 3.1, it can be concluded that:

$\gamma (\bar{x}_2, \bar{x}_3)+ (1-\gamma)(\hat{x}_2, \hat{x}_3) = \Psi_2( \gamma \bar{x}_1+ (1-\gamma)\hat{x})$, for all $0\le \gamma \le \gamma_1$.

In addition, $\gamma (\bar{x}_1, \bar{x}_2, \bar{x}_3)+(1-\gamma)(\hat{x}_1, \hat{x}_2, \hat{x}_3) \in {ri} \ F \subset S$. Therefore,

$\gamma (\bar{x}_1, \bar{x}_2, \bar{x}_3)+(1-\gamma)(\hat{x}_1, \hat{x}_2, \hat{x}_3) \in IR$, for all $0 \le \gamma \le \gamma_1$,

Eventually,

$(\tilde{x}_1, \tilde{y}_1, \tilde{z}_1) = \gamma_1(\bar{x}_1, \bar{x}_2, \bar{x}_3)+(1-\gamma_1)(\hat{x}_1, \hat{x}_2, \hat{x}_3) \in IR \cap {ri} \ F$.

If we repeat the process, we can construct from $(\tilde{x}_1, \tilde{y}_1, \tilde{z}_1)$ a new point called $(\tilde{x}_2, \tilde{y}_2, \tilde{z}_2)\in IR \cap {ri} \ F$ which lies along the line segment among $(\bar{x}_1, \bar{x}_2, \bar{x}_3)$ and $(\tilde{x}_1, \tilde{y}_1, \tilde{z}_1)$.

Therefore, we approach point $(\bar{x}_1, \bar{x}_2, \bar{x}_3)$ along the line segment among $(\bar{x}_1, \bar{x}_2, \bar{x}_3)$ and $(\hat{x}_1, \hat{x}_2, \hat{x}_3)$, by the points which are belongs to $IR$ and so by the continuity of $\Psi_2$, it can be concluded that $(\bar{x}_1, \bar{x}_2, \bar{x}_3) \in IR$ and this completes the proof.

Corollary 3.2. The inducible region of the LTLP problem can be written as the union of some faces of S that are not necessarily connected.

Corollary 3.3. If $IR \neq \emptyset$, an optimal solution to the LTLP problem occurs at a vertex of $IR$ and hence, at a vertex of $S$.

Proof. Notice that the problem (2.2) can be written equivalently as

$\begin{equation} \label{conv} \min \{f_1(x_1, x_2, x_3) : (x_1, x_2, x_3) \in conv \ IR \} \end{equation}$

(3.3)

where conv $IR$ denotes the convex hull of $IR$. It is clear that there exists a solution to the problem (3.3) which is a vertex of conv $IR$ ^[4]. Although, conv $IR$ and $IR$ are different sets their vertices are the same. Moreover, by Corollary 3.2, $IR$ is formed from the union of some faces of S. Therefore, the vertices of $IR$ (and conv $IR$) are also the vertices of $S$ and this fact completes the proof.

Through the above results, it has been demonstrated that there exists at least a vertex of $S$ which solves the problem (2.1). This fact allows us to develop enumerative algorithms which search amongst extreme points of the constraint region to solve the LTLP problem.

---

4. Modified trilevel Kth-Best algorithm

In this section, the modified trilevel Kth-Best algorithm is presented. In actual, the modified algorithm takes into account LTLP problems with unbounded middle and bottom level problems. These cases are not considered in the Kth-Best algorithm ^[19]. Also, it resolves some of drawbacks while finding an optimal solution for LTLP problems with opposing objectives. Moreover, in the next section, it is shown that in some LTLP problems, the proposed algorithm leads to reduction the amount of computations needed for finding an optimal solution.

The process of the modified trilevel Kth-Best algorithm is as follows:

The Algorithm

Step 1. Initialization: Set $k \longleftarrow 1$, $W^* = T = W \longleftarrow \emptyset$. Go to Step 2

Step 2. Find the optimal solution of the optimization problem (4.1). Let it be $(x_1^{[1]}, x_2^{[1]}, x_3^{[1]})$ and go to Step 3.

$\begin{equation} \label{relaxed} \min \{ f_1(x_1, x_2, x_3): (x_1, x_2, x_3) \in S \} \end{equation}$

(4.1)

Step 3. Solve the following problem.

$\begin{equation} \label{p1} \min \{ \alpha_{3 \ 3}^T x_3: x_3 \in \Omega_3(x_1^{[k]}, x_2^{[k]}) \}. \end{equation}$

(4.2)

If the problem (4.2) is unbounded go to step 7, else let $x'_3$ be the optimal solution and go to Step 4.

Step 4. If $x_3^{[k]} = x'_3$, go to step 5 else go to step 7. [If $x_3^{[k]} = x'_3$ then $x_3^{[k]} \in \Psi_3(x_1^{[k]}, x_2^{[k]})$.]

Step 5. Solve the following problem.

$\begin{equation} \label{p2} \min \{ \alpha_{2 \ 2}^T x_2+\alpha_{2 \ 3}^T x_3: (x_2 , x_3)\in S_2(x_1^{[k]}), x_3 = x_3^{[k]} \}. \end{equation}$

(4.3)

If problem (4.3) is unbounded go to step 7, else let $x'_2$ be the optimal solution and go to step 6.

Step 6. If $x_2^{[k]} = x'_2$, then $(x_2^{[k]}, x_3^{[k]}) \in \Psi_2(x_1^{[k]})$ and $(x_1^{[k]}, x_2^{[k]}, x_3^{[k]})$ is the optimal solution, exit. Else go to Step 7.

Step 7. Set $k \longleftarrow k+1$ and $T \longleftarrow T \cup (x_1^{[k]}, x_2^{[k]}, x_3^{[k]})$. Let $W$ be the adjacent extreme points set of current extreme point i.e., $(x_1^{[k]}, x_2^{[k]}, x_3^{[k]})$. Set $W^* \longleftarrow W^* \cup W \setminus T$. Go to Step 8

Step 8. If $W^* = \emptyset$ there is no optimal solution, exit. Else let $(x_1^{[k]}, x_2^{[k]}, x_3^{[k]})$ be the point with the smallest value in $W^*$ with respect to $f_1$, go to step 3.

Figure 1 illustrates the process of modified trilevel Kth-Best algorithm.

Remark 4.1. It is clear that if $IR \neq \emptyset$ and Assumption $3.3$ is valid, the LTLP problem has an optimal solution. However, in spite of the fact that the constraint region $S$ is bounded, the middle-level problem or the bottom level problem may be unbounded. In these cases, we have $\Psi_2(x_1) = \emptyset$ for all $x_1 \in S_{X_1}$ or $\Psi_3(x_1, x_2) = \emptyset$ for all $(x_1, x_2) \in S_{X_1 \times X_2}$. Hence, the inducible region will be empty set and consequently, the LTLP problem has no optimal solution. We have considered this case in the modified trilevel kth-Best algorithm. Indeed, when the optimality of the candidate vertex is examined, the unboundedness of the middle level or the bottom level problems are also inspected in step 3 and step 5. Eventually, if the middle-level or the bottom-level problem is unbounded, after the finite number of iterations (at most equal to the number of extreme points), the algorithm will terminate with the result that the trilevel programming problem has no optimal solution.

Proposition 4.1. Let the LTLP problem (2.1) has an optimal solution. Then the modified trilevel Kth-Best algorithm will terminate with an optimal solution of LTLP problem in a finite number of iterations.

Proof. Let $(x_1^{[k]}, x_2^{[k]}, x_3^{[k]})$ be the terminated point. The termination condition in Step 6 of the algorithm is equal to the fact that $(x_1^{[k]}, x_2^{[k]}, x_3^{[k]})$ belongs to the inducible region. Moreover, according to the algorithm procedure, we know that $(x_1^{[k]}, x_2^{[k]}, x_3^{[k]})$ is the optimal solution of the following problem:

$\min\{f_1(x_1, x_2, x_3):(x_1, x_2, x_3) \in S \setminus \cup_{i = 1}^{k-1}(x_1^{[i]}, x_2^{[i]}, x_3^{[i]}) \},$ (Theorem 2.3.4 of ^[3]). Therefore if termination occurs, this point has the smallest value between the points of $IR$ with respect to $f_1$.

It is worth mentioning that, by omitting the examined extreme points from $W^*$, the cycling is prevented. Moreover, since the extreme points of the constraint region are finite, the algorithm will terminate after a finite number of iterations.

---

5. Numerical examples

To illustrate the advantages of the modified trilevel Kth-Best algorithm, the following examples are solved according to the outline indicated in the previous section.

Example 5.1. Consider the following LTLP problem:

$\begin{align*} &\min\limits_{x_1 } \quad 2x_1+2x_2+5x_3\\ &\qquad x_1 \leq 8 \\ &\qquad x_2 \leq 5 \quad \ where~x_2, x_3 ~solve: \\ &\qquad \max\limits_{x_2} \quad 6x_1+x_2-3x_3 \\ &\qquad \qquad x_1+x_2 \leq 8 \\ &\qquad \qquad x_1+4x_2 \geq 8 \\ &\qquad \qquad 7x_1-2x_2\geq 0 \quad \ where ~x_3~ solves: \\ &\qquad \qquad \min\limits_{ x_3} \quad 2x_1+x_2-2x_3\\ &\qquad \qquad \qquad 5x_1+5x_2+14x_3 \le 40 \\ &\qquad \qquad \qquad x_1, x_2, x_3 \geq 0 \end{align*}$

In this example, we have $\Psi_3(x_1, x_2) = \frac{1}{14}(40-5x_1-5x_2)$ for all $0 \le x_1, x_2 \le 8$, $x_1+x_2 \le 8$. Moreover,

$\Psi_2(x_1) = \{ (\frac{7}{2}x_1, \frac{1}{14}(40-\frac{45}{2}x_1)): \frac{8}{15} \le x_1 \le \frac{16}{9} \} \cup \{ (8-x_1, 0): \frac{16}{9} \le x_1 \le 8 \}.$

It is clear that for $\frac{10}{7} \le x_1 \le \frac{16}{9}$, we have $\frac{7}{2}x_1 > 5$ and for $\frac{16}{9} \le x_1 < 3$, we have $8-x_1>5$. So, neither $S$ nor $IR$ include the following set:

$\{ (x_1, \frac{7}{2}x_1, \frac{1}{14}(40-\frac{45}{2}x_1):\frac{10}{7} < x_1 \le \frac{16}{9} \} \cup \{ (x_1, 8-x_1, 0): \frac{16}{9} \le x_1 < 3 \}$.

Actually,

$IR = \{ (x_1, \frac{7}{2}x_1, \frac{1}{14}(40-\frac{45}{2}x_1):\frac{8}{15} \le x_1 \le \frac{10}{7} \} \cup \{(x_1, 8-x_1 , 0): 3 \le x_1 \le 8 \}$

which is disconnected. This fact shows that despite the continuity of $\Psi_2$, the inducible region is disconnected. The hatched lines at Figure 2 represent the inducible region.

By Corollary 3.3, an optimal solution of the above example occurs at the point $(\frac{8}{15}, \frac{28}{15}, 2)$.

To solve the example by the modified trilevel Kth-Best algorithm, the process is as follows:

Iteration 1

1. $(x_1^{[1]}, x_2^{[1]}, x_3^{[1]}) = (\frac{8}{15}, \frac{28}{15}, 0)$.

2. $x'_3 = 2 \neq x_3^{[1]}$

3. $T = \{ (\frac{8}{15}, \frac{28}{15}, 0) \}$.

4. $W^* = \{ (8, 0, 0), (\frac{10}{7}, 5, 0), (\frac{8}{15}, \frac{28}{15}, 2) \}$.

Iteration 2

1. $(x_1^{[2]}, x_2^{[2]}, x_3^{[2]}) = (\frac{10}{7}, 5, 0)$.

2. $x'_3 = \frac{55}{98} \neq x_3^{[2]}$

3. $T = \{ (\frac{8}{15}, \frac{28}{15}, 0), (\frac{10}{7}, 5, 0) \}$.

4. $W^* = \{ (8, 0, 0), (\frac{10}{7}, 5, \frac{55}{98}), (\frac{8}{15}, \frac{28}{15}, 2), (3, 5, 0) \}$.

Iteration 3

1. $(x_1^{[3]}, x_2^{[3]}, x_3^{[3]}) = (\frac{8}{15}, \frac{28}{15}, 2)$.

2. $x'_3 = 2 = x_3^{[3]}$

3. $x'_2 = \frac{28}{15} = x_2^{[3]}$

4. The point $(x_1^{[3]}, x_2^{[3]}, x_3^{[3]}) = (\frac{8}{15}, \frac{28}{15}, 2)$ is the optimal solution.

As demonstrated in the solving process of this problem, although the number of iterations and the optimal solution found by the two algorithms are the same, the number of optimization problems needed to be solved in each iteration of the Kth-Best algorithm ^[19] are more than the number of optimization problems needed to be solved in the modified Kth-Best algorithm. Then the amount of computations in each iteration of the modified Kth-Best algorithm is less than that of the corresponding iteration in the Kth-Best algorithm..

The two following examples show some discrepancies in the Kth-Best algorithm ^[19] that cause an erroneous result.

Example 5.2.

$\begin{align*} &\min\limits_{x} f_1 (x, y, z) = -x -4z+2y \quad where ~y, ~z ~soleve:\\ &s.t \quad \min\limits_{y} f_2(x, y, z) = 3y- 2z \quad where~ z~solves:\\ &\quad s.t \quad \min\limits_{z} f_3 (x, y, z) = 2z-y \\ &\qquad s.t \quad x+y+z \le 2 \\ &\qquad \qquad 0 \le x, y, z \le 1 \end{align*}$

In this example, we have $IR = \{(x, 0, 0): 0 \le x \le 1 \}$. The constraint region and inducible region are shown in Figure 3 by gray area and hatched line, respectively. It is easy to see that the constraint region is a compact set and lower levels reaction sets are single-valued. Therefore, all the assumptions of the trilevel Kth-Best algorithm ^[19] hold.

The Kth-Best algorithm process ^[19] for solving this problem is as follows:

Iteration 1 : $(x_{[1]}, y_{[1]}, z_{[1]}) = (1, 0, 1)$, $(y'_{[1]}, z'_{[1]}) = (0, 1)$, $z^{''}_{[1]} = 0$ and $z_{[1]} \neq z^{''}_{[1]}$.

Therefore, $(x_{[1]}, y_{[1]}, z_{[1]}) = ( 1, 0, 1)$ is not the optimal solution of the LTLP problem and we have to find the next best adjacent extreme point.

Iteration 2 : $(x_{[2]}, y_{[2]}, z_{[2]}) = (0, 0, 1)$, $(y'_{[2]}, z'_{[2]}) = (0, 1)$, $z^{''}_{[2]} = 0$. Since $z^{''}_{[2]} \neq z_{[2]}$, then this point is not the optimal solution either. Following the algorithm, at iteration 7, we obtain:

Iteration 7 : $(x_{[7]}, y_{[7]}, z_{[7]}) = (0, 1, 0)$. This is the last accessible extreme point which should be examined. At this iteration, we have $(y'_{[7]}, z'_{[7]}) = (0, 1)$ and since $z'_{[7]} \neq z_{[7]}$, this point is not the optimal solution either. Therefore, the trilevel Kth-Best algorithm ^[19] fails to find an optimal solution to this problem.

By solving the example via the modified trilevel Kth-Best algorithm, the process is as follows:

Iteration 1

1. $(x^{[1]}, y^{[1]}, z^{[1]}) = (1, 0, 1)$.

2. $z' = 0 \neq z^{[1]}$

3. $W^* = \{ (0, 0, 1), (0, 1, 1), (1, 0, 0), (1, 1, 0) \}$.

Iteration 2

1. $(x^{[2]}, y^{[2]}, z^{[2]}) = (0, 0, 1)$

2. $z' = 0 \neq z^{[2]}$

3. $W^* = \{ (0, 1, 1), (1, 0, 0), (0, 0, 0), (1, 1, 0) \}$

Continuing this method, at iteration 4 we get:

$(x^{[4]}, y^{[4]}, z^{[4]}) = (1, 0, 0)$, $z' = 0$ and $y' = 0$. Therefore, the point $(1, 0, 0)$ is the optimal solution which is equal to the solution obtained by the multi-parametric approach ^[5].

Note that, in the trilevel Kth-Best algorithm ^[19], the bottom-level optimal solution which is found for some fixed values of upper and middle-level variables, is not considered as a constraint for the second level problem. This causes the Kth-best algorithm is not capable of finding an optimal solution for some LTLP problems. This fact is considered in step 5 of the modified trilevel Kth-Best algorithm by fixing the lower level variable which is found as the optimal solution of problem (4.2) and substituting it in the problem (4.3).

Example 5.3.

$\begin{align}\label{empty} &\min\limits_{x_1} \quad x_1-4x_2+2x_3 \nonumber \\ &\qquad -x_1-x_2 \le -3 \nonumber \\ &\qquad -3x_1+2x_2-x_3 \geq -10 \quad where ~x_2, x_3~ solve: \nonumber \\ &\qquad \min\limits_{x_2} \quad x_1+x_2-x_3 \nonumber \\ &\qquad \qquad -2x_1+x_2-2x_3 \le -1 \\ &\qquad \qquad 2x_1+x_2+4x_3 \le 14 \quad where ~x_3~ solves: \nonumber \\ &\qquad \qquad \min\limits_{x_3} \quad x_1-2x_2-2x_3 \nonumber \\ &\qquad \qquad \qquad 2x_1-x_2-x_3 \le 2 \nonumber \\ &\qquad \qquad \qquad x_1, x_2, x_3 \geq 0 \nonumber \end{align}$

(5.1)

The process of the modified trilevel Kth-Best algorithm to solve this problem is as follows:

Iteration 1

1. $(x_1^{[1]}, x_2^{[1]}, x_3^{[1]}) = (3.75, 6.5, 0)$.

2. The bottom level problem corresponding to $(x_1, x_2) = (3.75, 6.5)$ is unbounded.

3. $T = \{(3.75, 6.5, 0) \}$.

4. $W = \{(4, 6, 0), (\frac{4}{3}, \frac{5}{3}, 0), (0, 4, 2.5) \}.$

5. $W^* = W$.

Iteration 2

1. $(x_1^{[2]}, x_2^{[2]}, x_3^{[2]}) = (4, 6, 0)$.

2. The bottom level problem corresponding to $(x_1, x_2) = (4, 6)$ is unbounded.

3. $T = \{(3.75, 6.5, 0), (4, 6, 0) \}$.

4. $W = \{(3.75, 6.5, 0), ( \frac{5}{3}, \frac{4}{3}, 0), (\frac{31}{13}, \frac{8}{13}, \frac{28}{13}) \}.$

5. $W^* = \{(\frac{4}{3}, \frac{5}{3}, 0), (0, 4, 2.5), (\frac{5}{3}, \frac{4}{3}, 0), (\frac{31}{13}, \frac{8}{13}, \frac{28}{13}) \}.$

Iteration 3

1. $(x_1^{[3]}, x_2^{[3]}, x_3^{[3]}) = (0, 4, 2.5)$.

2. The bottom level problem corresponding to $(x_1, x_2) = (0, 4)$ is unbounded.

3. $T = \{(3.75, 6.5, 0), (4, 6, 0), (0, 4, 2.5)\}$.

4. $W = \{(0, 3, 2.75), (0, 3, 2), (3.75, 6.5, 0)\}$

5. $W^* = \{(\frac{4}{3}, \frac{5}{3}, 0), (0, 3, 2), (\frac{5}{3}, \frac{4}{3}, 0), (\frac{31}{13}, \frac{8}{13}, \frac{28}{13}), (0, 3, 2.75) \}.$

Iteration 4

1. $(x_1^{[4]}, x_2^{[4]}, x_3^{[4]}) = (0, 3, 2)$.

2. The bottom level problem corresponding to $(x_1, x_2) = (0, 3)$ is unbounded.

3. $T = \{(3.75, 6.5, 0), (4, 6, 0), (0, 4, 2.5), (0, 3, 2)\}$.

4. $W = \{(0, 4, 2.5), (0, 3, 2.75) \}.$

5. $W^* = \{(\frac{4}{3}, \frac{5}{3}, 0), (\frac{5}{3}, \frac{4}{3}, 0), (\frac{31}{13}, \frac{8}{13}, \frac{28}{13}), (0, 3, 2.75) \}.$

Iteration 5

1. $(x_1^{[5]}, x_2^{[5]}, x_3^{[5]}) = (0, 3, 2.75)$.

2. The bottom level problem corresponding to $(x_1, x_2) = (0, 3)$ is unbounded.

3. $T = \{(3.75, 6.5, 0), (4, 6, 0), (0, 4, 2.5), (0, 3, 2), (0, 3, 2.75)\}$.

4. $W = \{(0, 3, 2), (0, 4, 2.5), (\frac{31}{13}, \frac{8}{13}, \frac{28}{13}) \}.$

5. $W^* = \{(\frac{4}{3}, \frac{5}{3}, 0), (\frac{5}{3}, \frac{4}{3}, 0), (\frac{31}{13}, \frac{8}{13}, \frac{28}{13}) \}.$

Iteration 6

1. $(x_1^{[6]}, x_2^{[6]}, x_3^{[6]}) = (\frac{4}{3}, \frac{5}{3}, 0)$.

2. The bottom level problem corresponding to $(x_1, x_2) = (\frac{4}{3}, \frac{5}{3})$ is unbounded.

3. $T = \{(3.75, 6.5, 0), (4, 6, 0), (0, 4, 2.5), (0, 3, 2), (0, 3, 2.75), (\frac{4}{3}, \frac{5}{3}, 0)\}$.

4. $W = \{(3.75, 6.5, 0), (\frac{5}{3}, \frac{4}{3}, 0)(0, 3, 2) \}.$

5. $W^* = \{ (\frac{5}{3}, \frac{4}{3}, 0), (\frac{31}{13}, \frac{8}{13}, \frac{28}{13}) \}.$

Iteration 7

1. $(x_1^{[7]}, x_2^{[7]}, x_3^{[7]}) = (\frac{5}{3}, \frac{4}{3}, 0)$.

2. The bottom level problem corresponding to $(x_1, x_2) = (\frac{5}{3}, \frac{4}{3})$ is unbounded.

. $T = \{(3.75, 6.5, 0), (4, 6, 0), (0, 4, 2.5), (0, 3, 2), (0, 3, 2.75), (\frac{4}{3}, \frac{5}{3}, 0), (\frac{5}{3}, \frac{4}{3}, 0)\}$.

4. $W = \{ (4, 6, 0), (\frac{31}{13}, \frac{8}{13}, \frac{28}{13}) , (\frac{4}{3}, \frac{5}{3}, 0) \}.$

5. $W^* = \{ (\frac{31}{13}, \frac{8}{13}, \frac{28}{13}) \}.$

Iteration 8

1. $(x_1^{[8]}, x_2^{[8]}, x_3^{[8]}) = (\frac{31}{13}, \frac{8}{13}, \frac{28}{13})$.

2. The bottom level problem corresponding to $(x_1, x_2) = (\frac{31}{13}, \frac{8}{13})$ is unbounded.

$3. \ T = \{ (3.75, 6.5, 0), (4, 6, 0), (0, 4, 2.5), (0, 3, 2), (0, 3, 2.75), (\frac{4}{3}, \frac{5}{3}, 0), (\frac{5}{3}, \frac{4}{3}, 0), \\ (\frac{31}{13}, \frac{8}{13}, \frac{28}{13})\}.$

4. $W^* = \emptyset.$

5. There is no optimal solution.

In the above example, the constraint region is a bounded polyhedron. Let $(x_1^*, x_2^*) \in S_{X_1, X_2}$ be chosen arbitrarily. To find the mapping $\Psi_3(x_1^*, x_2^*)$, the following parametric linear programming should be solved:

$\begin{align} \label{unbdd} &\min\limits_{x_3} \quad x_1-2x_2-2x_3 \nonumber \\ &\qquad 2x_1-x_2-x_3 \le 2 \\ &\qquad x_1 = x_1^*\ , \ x_2 = x_2^* \ , \ x_3 \geq 0 \nonumber %&\qquad x_2 = x_2^* \nonumber \\ %&\qquad x_3 \geq 0 \nonumber \end{align}$

(5.2)

It is easy to see that the problem (5.2) is unbounded. Therefore, $\Psi_3(x_1^*, x_2^*) = \emptyset$ for all $(x_1^*, x_2^*) \in S_{X_1, X_2}$. Consequently, $IR$ is also empty and the problem (5.1) does not have any feasible solution and so any optimal solution. The constraint region is represented at Figure 4. Therefore, the modified trilevel Kth-Best algorithm concludes that the problem does not have an optimal solution, while the trilevel Kth-Best algorithm ^[19] has obtained the point $(4, 6, 0)$ as the optimal solution (^[19], section 5.1) which is incorrect.

---

6. Conclusion

In this study, the linear trilevel programming problem whereby each planner has his (her) own constraints, was considered. Some geometric properties of the inducible region were discussed. Under certain assumptions, it is proved that if the inducible region is non-empty, then it is composed of the union of some non-empty faces of the constraint region $S$ and at least an optimal solution occurs at an extreme point of $IR$ which is also an extreme point of $S$. Then, we proposed a modified trilevel Kth-Best algorithm to find an optimal solution. Finally, we presented some numerical examples to highlight some discrepancies between the modified trilevel Kth-Best algorithm and the trilevel Kth-Best algorithm.

---

Conflict of Interest

The authors declare no conflict of interest in this paper.

---