# A Novel Method for Solving the Fully Fuzzy Bilevel Linear Programming Problem

Authors: Aihong Ren
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

We address a fully fuzzy bilevel linear programming problem in which all the coefficients and variables of both objective functions and constraints are expressed as fuzzy numbers. This paper is to develop a new method to deal with the fully fuzzy bilevel linear programming problem by applying interval programming method. To this end, we first discretize membership grade of fuzzy coefficients and fuzzy decision variables of the problem into a finite number ofα-level sets. By using α-level sets of fuzzy numbers, the fully fuzzy bilevel linear programming problem is transformed into an interval bilevel linear programming problem for each α-level set. The main idea to solve the obtained interval bilevel linear programming problem is to convert the problem into two deterministic subproblems which correspond to the lower and upper bounds of the upper level objective function. Based on the Kth-best algorithm, the two subproblems can be solved sequentially. Based on a series of α-level sets, we introduce a linear piecewise trapezoidal fuzzy number to approximate the optimal value of the upper level objective function of the fully fuzzy bilevel linear programming problem. Finally, a numerical example is provided to demonstrate the feasibility of the proposed approach.


---

## Body

## 1. Introduction

The bilevel programming problem is a nested optimization problem including two optimization problems in which the feasible region of the upper level problem is determined implicitly by the solution set of the lower level problem. This kind of problem is nonconvex and very hard to solve due to its structure. In the past few decades, the bilevel programming problem has been researched from both the theoretical and computational points of view [1–3] and has been applied so extensively in resource allocation, finance budget, price control, transaction network, and so forth [4].In conventional bilevel programming models, their parameters are assumed to be well defined and precise. However, in many real-world applications, particularly in some areas linked to human resource planning or actual decision making process, we often need to make a decision on the basis of uncertain data or information. Therefore, inexact optimization methods are desired for supporting environment under uncertainty. The fuzzy set theory provides powerful tools for dealing with imprecise or vague information. In recent years, the fuzzy bilevel programming problem has also become a rapidly progressing research area and has received much attention of some researchers. Sakawa et al. [5] first studied the fuzzy bilevel programming problem and proposed a fuzzy programming method to deal with it on the basis of the definition of optimal solution for bilevel programming proposed by Bard [6]. Zhang and Lu [7] developed an extended Kuhn-Tucher approach to deal with the fuzzy bilevel linear programming problem based on the new definition of optimal solution. The fuzzy Kuhn-Tucker approach, the fuzzy Kth-best approach, and the fuzzy branch-and-bound approach were designed to handle the fuzzy bilevel programming problem by applying fuzzy set techniques [8]. Dempe and Starostina [9] formulated the fuzzy bilevel programming problem and described one possible approach for formulating a crisp optimization problem being attached to it. In all of the above-mentioned works, those cases of the fuzzy bilevel programming problem have been studied in which all or some coefficients involved in the objective functions and the constraints are assumed to be fuzzy but all variables of the problem are deterministic.As a matter of fact, the fully fuzzy linear programming in which all the coefficients as well as the variables are represented by fuzzy numbers is an attractive topic for researchers. Buckley and Feuring [10] considered this kind of problem and employed an evolutionary algorithm to deal with it. A new method was proposed to solve a fully fuzzy linear programming problem by applying the concept of comparison of fuzzy numbers [11]. Hosseinzadeh Lotfi et al. [12] transformed the fully fuzzy linear programming problem into two corresponding linear programming problems based on the concept of the symmetric triangular fuzzy number and developed a lexicography method to solve such a problem. Kumar et al. [13] proposed a new method to solve the fuzzy optimal solutions of the fully fuzzy linear programming problems with equality constraints. Subsequently, Najafi and Edalatpanah [14] pointed out that Kumar et al. model [13] was not correct and provided a revised version. Recently, Fan et al. [15] investigated the feasibility of fuzzy solutions of the generalized fuzzy linear programming problem and developed a stepwise interactive algorithm to solve the problem. In all these methods, the fully fuzzy linear programming problem is firstly converted into a crisp linear programming problem and then the obtained crisp linear programming problem is solved to find the fuzzy optimal solutions of the problem. In addition, it should be noted that all these works are considered in the case of one single level fully fuzzy linear programming.In this paper, we address a fully fuzzy bilevel linear programming problem in which all the coefficients and variables of both objective functions and the constraints are expressed as fuzzy numbers. To our knowledge, until now there are few studies on this type of problem. More recently, Safaei and Saraj [16] discussed the fully fuzzy bilevel linear programming problem by decomposing this problem into three crisp linear programming problems and then dealing with these three deterministic problems to obtain the fuzzy optimal solutions of the problem. However, this work on fuzzy solutions in a fully fuzzy bilevel linear problem is only suitable for triangular fuzzy numbers, which significantly restricts the application scope of the models.The interval mathematical programming method is an effective approach in tackling uncertainties. This approach does not require distributional information for input parameters and enables a relatively low computational requirement without complicated intermediate models. Over the past few decades, the interval mathematical programming has been heavily studied by many scholars and successfully applied to a variety of practical problems [17–22].The purpose of this paper is to develop a new method to deal with the fully fuzzy bilevel linear programming problem by applying interval programming method. According to the decomposition principle, the optimal value of the upper level objective function of the fully fuzzy bilevel linear programming problem can be expressed as the families of itsα-level sets. Based on this fact, we first discretize membership grade of fuzzy coefficients and fuzzy decision variables of the problem into a finite number of α-level sets. The fully fuzzy bilevel linear programming problem is transformed into an interval bilevel linear programming problem for any α-level set. The obtained interval bilevel linear programming problem is converted into two deterministic subproblems which correspond to the lower and upper bounds of its upper level objective function value. Then the two subproblems can be solved sequentially based on the Kth-best algorithm. Finally, the linear piecewise trapezoidal fuzzy number is introduced to approximate the optimal value of the upper level objective function of the fully fuzzy bilevel linear programming problem.This paper is organized as follows. In Section2 some basic definitions and results related to interval numbers and fuzzy numbers are reviewed. In Section 3 a new method is proposed to deal with the fully fuzzy bilevel programming problem by applying interval programming method. A numerical example is given to illustrate the proposed method and the obtained results are discussed in Section 4. Section 5 contains the concluding remarks.


## 2. Preliminaries

In this section, some basic notations and preliminary results of interval numbers and fuzzy numbers are presented.


### 2.1. Interval Numbers

LetR denote the set of all real numbers.An ordered pair in a bracket defines an interval as(1)
c
±
=
c
-
,
c
+
=
x
∈
R
∣
c
-
≤
x
≤
c
+
,where c
- and c
+ are the lower and upper bounds of c
±, respectively. When c
-
=
c
+, c
± becomes a deterministic number.Forc
1
±
=
[
c
1
-
,
c
1
+
], c
2
±
=
[
c
2
-
,
c
2
+
], and c
±
=
[
c
-
,
c
+
], we have(i)
c
1
±
⊕
c
2
±
=
[
c
1
-
+
c
2
-
,
c
1
+
+
c
2
+
];
(ii)
c
1
±
⊗
c
2
±
=
[
min
⁡
{
c
1
-
c
2
-
,
c
1
-
c
2
+
,
c
1
+
c
2
-
,
c
1
+
c
2
+
}, max
⁡
{
c
1
-
c
2
-, c
1
-
c
2
+, c
1
+
c
2
-
,
c
1
+
c
2
+
}
];
(iii)
-
c
±
=
[
-
c
+
,
-
c
-
].Thus(2)
c
1
±
⊖
c
2
±
=
c
1
-
-
c
2
+
,
c
1
+
-
c
2
-
,
k
c
±
=
k
c
-
,
k
c
+
,
k
≥
0
,
k
c
+
,
k
c
-
,
k
<
0
.Definition 1 (see [23]).
Forc
±, the following relationships hold:(i)
c
±
≥
0, if and only if c
-
≥
0 and c
+
≥
0;
(ii)
c
±
≤
0, if and only if c
-
≤
0 and c
+
≤
0.Definition 2 (see [23]).
Forc
±, Sign
⁡
c
± can be defined as follows: (3)
Sign
⁡
c
±
=
1
,
c
±
≥
0
,
-
1
,
c
±
<
0
.Definition 3 (see [23]).
Forc
±, its absolute value c
± can be given as follows: (4)
c
±
=
c
±
,
c
±
≥
0
,
-
c
±
,
c
±
<
0
.Hence, (5)
c
-
=
c
-
,
c
±
≥
0
,
-
c
+
,
c
±
<
0
,
c
+
=
c
+
,
c
±
≥
0
,
-
c
-
,
c
±
<
0
.


### 2.2. Fuzzy Numbers

Fuzzy numbers are one way to describe the vagueness and lack of precision of data. We give some basic concepts of fuzzy numbers as follows.Definition 4 (see [24]).
A fuzzy numberc
~ is defined as a fuzzy set on R, whose membership function μ
c
~
:
R
→
[
0,1
] satisfies the following conditions: (i)
there existsx
∈
R such that μ
c
~
(
x
)
=
1;
(ii)
μ
c
~ is upper semicontinuous;
(iii)
μ
c
~ is convex;
(iv)
the support ofc
~, Supp
c
~
=
{
x
∈
R
,
u
c
~
(
x
)
>
0
}, and its closure is compact.Theα-level set of a fuzzy number c
~ is defined by an ordinary set c
~
α
=
x
∣
μ
c
~
x
≥
α for α
∈
[
0,1
]. It is obvious that the α-level set of a fuzzy number c
~ is a closed interval, denoted as c
α
±
=
[
c
α
-
,
c
α
+
], for any α
∈
[
0,1
], c
α
-
≤
c
α
+.Definition 5 (see [25]).
A fuzzy numberc
~ is nonnegative if and only if its membership function μ
c
~
(
x
) satisfies μ
c
~
(
x
)
=
0 for ∀
x
<
0.


## 2.1. Interval Numbers

LetR denote the set of all real numbers.An ordered pair in a bracket defines an interval as(1)
c
±
=
c
-
,
c
+
=
x
∈
R
∣
c
-
≤
x
≤
c
+
,where c
- and c
+ are the lower and upper bounds of c
±, respectively. When c
-
=
c
+, c
± becomes a deterministic number.Forc
1
±
=
[
c
1
-
,
c
1
+
], c
2
±
=
[
c
2
-
,
c
2
+
], and c
±
=
[
c
-
,
c
+
], we have(i)
c
1
±
⊕
c
2
±
=
[
c
1
-
+
c
2
-
,
c
1
+
+
c
2
+
];
(ii)
c
1
±
⊗
c
2
±
=
[
min
⁡
{
c
1
-
c
2
-
,
c
1
-
c
2
+
,
c
1
+
c
2
-
,
c
1
+
c
2
+
}, max
⁡
{
c
1
-
c
2
-, c
1
-
c
2
+, c
1
+
c
2
-
,
c
1
+
c
2
+
}
];
(iii)
-
c
±
=
[
-
c
+
,
-
c
-
].Thus(2)
c
1
±
⊖
c
2
±
=
c
1
-
-
c
2
+
,
c
1
+
-
c
2
-
,
k
c
±
=
k
c
-
,
k
c
+
,
k
≥
0
,
k
c
+
,
k
c
-
,
k
<
0
.Definition 1 (see [23]).
Forc
±, the following relationships hold:(i)
c
±
≥
0, if and only if c
-
≥
0 and c
+
≥
0;
(ii)
c
±
≤
0, if and only if c
-
≤
0 and c
+
≤
0.Definition 2 (see [23]).
Forc
±, Sign
⁡
c
± can be defined as follows: (3)
Sign
⁡
c
±
=
1
,
c
±
≥
0
,
-
1
,
c
±
<
0
.Definition 3 (see [23]).
Forc
±, its absolute value c
± can be given as follows: (4)
c
±
=
c
±
,
c
±
≥
0
,
-
c
±
,
c
±
<
0
.Hence, (5)
c
-
=
c
-
,
c
±
≥
0
,
-
c
+
,
c
±
<
0
,
c
+
=
c
+
,
c
±
≥
0
,
-
c
-
,
c
±
<
0
.


## 2.2. Fuzzy Numbers

Fuzzy numbers are one way to describe the vagueness and lack of precision of data. We give some basic concepts of fuzzy numbers as follows.Definition 4 (see [24]).
A fuzzy numberc
~ is defined as a fuzzy set on R, whose membership function μ
c
~
:
R
→
[
0,1
] satisfies the following conditions: (i)
there existsx
∈
R such that μ
c
~
(
x
)
=
1;
(ii)
μ
c
~ is upper semicontinuous;
(iii)
μ
c
~ is convex;
(iv)
the support ofc
~, Supp
c
~
=
{
x
∈
R
,
u
c
~
(
x
)
>
0
}, and its closure is compact.Theα-level set of a fuzzy number c
~ is defined by an ordinary set c
~
α
=
x
∣
μ
c
~
x
≥
α for α
∈
[
0,1
]. It is obvious that the α-level set of a fuzzy number c
~ is a closed interval, denoted as c
α
±
=
[
c
α
-
,
c
α
+
], for any α
∈
[
0,1
], c
α
-
≤
c
α
+.Definition 5 (see [25]).
A fuzzy numberc
~ is nonnegative if and only if its membership function μ
c
~
(
x
) satisfies μ
c
~
(
x
)
=
0 for ∀
x
<
0.


## 3. Fully Fuzzy Bilevel Linear Programming Problem

Consider the following fully fuzzy bilevel linear programming problem in which all the coefficients as well as the variables are represented by fuzzy numbers:(6)
max
⁡
x
~
1
F
~
=
c
~
11
⊗
x
~
1
⊕
c
~
12
⊗
x
~
2
max
⁡
x
~
2
f
~
=
c
~
22
⊗
x
~
2
s
.
t
.
A
~
1
⊗
x
~
1
⊕
A
~
2
⊗
x
~
2
≤
b
~
,
x
~
1
≥
0
,
x
~
2
≥
0
,where x
~
1
=
(
x
~
11
,
x
~
12
,
…
,
x
~
1
n
1
) is an n
1-dimensional fuzzy decision vector of the upper level and x
~
2
=
(
x
~
21
,
x
~
22
,
…
,
x
~
2
n
2
) is an n
2-dimensional fuzzy decision vector of the lower level, respectively; c
~
1
j
=
(
c
~
1
j
1
,
c
~
1
j
2
,
…
,
c
~
1
j
n
j
), j
=
1,2, are n
j-dimensional fuzzy vectors and c
~
22
=
(
c
~
221
,
c
~
222
,
…
,
c
~
22
n
2
) is an n
2-dimensional fuzzy vector; b
~
=
(
b
~
1
,
b
~
2
,
…
,
b
~
m
) is an m-dimensional fuzzy vector and A
~
j
=
(
a
~
j
s
t
j
)
m
×
n
j are m
×
n
j fuzzy matrices in which a
~
j
s
t
j, for all s
∈
m, t
j
∈
n
j, are fuzzy numbers.Because of the existence of fuzzy coefficients and fuzzy decision variables in the objective functions and the constraints, problem (6) is not well defined and has no clear mathematical meaning. Thus deterministic bilevel optimization techniques cannot be directly applied to solve this kind of problem. Even for one single level, it has been pointed out by Buckley and Feuring [10] that searching for the optimal solutions of a fully fuzzy linear programming problem is a very difficult task. In this section, a potential method is developed to handle the fully fuzzy bilevel linear programming problem.


### 3.1. Modeling Formulation

Observing that all the coefficients and decision variables of the upper level objective function of problem (6) are fuzzy numbers, the upper level objective function is also a fuzzy number. It is well known that fuzzy numbers can be defined by the families of their α-level sets according to the decomposition principle [26]. Then the optimal value of the upper level objective function of problem (6) can be expressed as the families of its α-level sets.Based on this fact, we first discretize membership grade of fuzzy coefficients and fuzzy decision variables of problem (6) into a finite number of α-level sets. For any α
∈
[
0,1
], the α-level sets of x
~
j
k
j, c
~
1
j
k
j, j
=
1,2, k
j
=
1,2
,
…
,
n
j, c
~
22
k
2, a
~
j
s
t
j, and b
~
s, s
=
1,2
,
…
,
m, t
j
=
1,2
,
…
,
n
j, can be denoted as (
x
~
j
k
j
)
α
=
[
(
x
j
k
j
)
α
-
,
(
x
j
k
j
)
α
+
], (
c
~
1
j
k
j
)
α
=
[
(
c
1
j
k
j
)
α
-
,
(
c
1
j
k
j
)
α
+
], (
c
~
22
k
2
)
α
=
[
(
c
22
k
2
)
α
-
,
(
c
22
k
2
)
α
+
], (
a
~
j
s
t
j
)
α
=
[
(
a
j
s
t
j
)
α
-
,
(
a
j
s
t
j
)
α
+
], and (
b
~
s
)
α
=
[
(
b
s
)
α
-
,
(
b
s
)
α
+
].Considering that theα-level sets of fuzzy numbers are actually closed intervals, the operations on fuzzy numbers are indeed performed by the interval arithmetic operations for α-level sets. Then the fully fuzzy bilevel linear programming problem (6) can be transformed into the following interval bilevel linear programming problem for any α-level set:(7)
max
⁡
F
α
±
=
∑
k
1
=
1
n
1
‍
c
11
k
1
α
±
⊗
x
1
k
1
α
±
max
⁡
⊕
∑
k
2
=
1
n
2
c
12
k
2
α
±
⊗
x
2
k
2
α
±
max
⁡
f
α
±
=
∑
k
2
=
1
n
2
‍
c
22
k
2
α
±
⊗
x
2
k
2
α
±
s
.
t
.
∑
k
1
=
1
n
1
‍
a
1
s
k
1
α
±
⊗
x
1
k
1
α
±
max
⁡
⊕
∑
k
2
=
1
n
1
a
2
s
k
2
α
±
⊗
x
2
k
2
α
±
≤
b
s
α
±
,
max
⁡
s
=
1,2
,
…
,
m
,
max
⁡
x
1
k
1
α
±
≥
0
,
k
1
=
1,2
,
…
,
n
1
,
max
⁡
x
2
k
2
α
±
≥
0
,
k
2
=
1,2
,
…
,
n
2
.Remark 6.
For problem (6), the upper level objective function F
~ can be rewritten as ∑
k
1
=
1
n
1
‍
c
~
11
k
1
⊗
x
~
1
k
1
⊕
∑
k
2
=
1
n
2
‍
c
~
12
k
2
⊗
x
~
2
k
2. Then we have (
F
~
)
α
=
F
α
±
=
(
∑
k
1
=
1
n
1
‍
c
~
11
k
1
⊗
x
~
1
k
1
⊕
∑
k
2
=
1
n
2
‍
c
~
12
k
2
⊗
x
~
2
k
2
)
α
=
∑
k
1
=
1
n
1
‍
(
c
11
k
1
)
α
±
⊗
(
x
1
k
1
)
α
±
⊕
∑
k
2
=
1
n
2
‍
(
c
12
k
2
)
α
±
⊗
(
x
2
k
2
)
α
± for any α-level set. Obviously, the lower level objective function and the constraints of problem (7) can be obtained by similar algebraic operation.Under differentα-level sets, a series of interval bilevel linear programming problems are generated. Here we are interested in computing the lower and upper bounds of the upper level objective functions of these interval bilevel linear programming problems. Based on these results, the optimal value of the upper level objective function of problem (6) can be decomposed as (8)
F
~
*
=
⋃
α
∈
[
0,1
]
α
F
α
*
-
,
F
α
*
+
.Hence, we will discuss how to determine the lower and upper bounds of the upper level objective function of the interval bilevel programming problem (7) in the following section.Since all the coefficients and the decision variables of problem (7) are interval numbers, the optimal upper level objective function values and the feasible regions of the problem are directly affected by different specific values of the coefficients and the decision variables chosen from their ranges. To deal with problem (7), we analyze model characteristics and the interrelationships among the coefficients and the decision variables in both objective functions and the constraints.Clearly, the lower level problem of problem (7) is a conventional interval linear programming. Huang et al. [17] proposed the two-step method to solve this kind of problem. The basic idea of this method is to first transform the interval linear programming problem into two deterministic subproblems which correspond to the lower and upper bounds of the objective function value and then solve the two subproblems sequentially to obtain the solutions of the problem. However, this method may result in constraint violation in its solution space [22]. To avoid this, Fan and Huang [22] developed a robust two-step method for solving the interval linear programming problem. In this way, we discuss the lower and upper bounds of the objective function of the lower level problem and then give the optimal bounds of the upper level objective function of the interval bilevel linear programming problem (7).For simplicity, problem (7) can be rewritten as (9)
max
⁡
F
α
±
=
c
11
α
±
×
x
1
α
±
+
c
12
α
±
×
x
2
α
±
max
⁡
f
α
±
=
c
22
α
±
×
x
2
α
±
s
.
t
.
A
1
α
±
×
x
1
α
±
+
A
2
α
±
×
x
2
α
±
≤
b
α
±
,
x
1
α
±
≥
0
,
x
2
α
±
≥
0
,where (
c
1
j
)
α
±
=
(
(
c
1
j
1
)
α
±
,
(
c
1
j
2
)
α
±
,
…
,
(
c
1
j
n
j
)
α
±
), j
=
1,2, (
x
j
)
α
±
=
(
(
x
j
1
)
α
±
,
(
x
j
2
)
α
±
,
…
,
(
x
j
n
j
)
α
±
), (
c
22
)
α
±
=
(
(
c
221
)
α
±
,
(
c
222
)
α
±
,
…
,
(
c
22
n
2
)
α
±
), (
A
j
)
α
±
=
(
(
a
j
s
t
j
)
α
±
), and b
α
±
=
(
(
b
1
)
α
±
,
(
b
2
)
α
±
,
…
,
(
b
m
)
α
±
).We call the following problem a characteristic version of problem (7):(10)
max
⁡
F
α
=
c
11
α
×
x
1
α
+
c
12
α
×
x
2
α
max
⁡
f
α
=
c
22
α
×
x
2
α
s
.
t
.
A
1
α
×
x
1
α
+
A
2
α
×
x
2
α
≤
b
α
,
x
1
α
≥
0
,
x
2
α
≥
0
,where (
c
1
j
)
α
∈
[
(
c
1
j
)
α
-
,
(
c
1
j
)
α
+
], j
=
1,2, (
x
j
)
α
∈
[
(
x
j
)
α
-
,
(
x
j
)
α
+
], (
A
j
)
α
∈
[
(
A
j
)
α
-, (
A
j
)
α
+
], and b
α
∈
[
b
α
-
,
b
α
+
].For anyα
∈
[
0,1
], (
A
1
)
α
∈
[
(
A
1
)
α
-
,
(
A
1
)
α
+
], (
A
2
)
α
∈
[
(
A
2
)
α
-
,
(
A
2
)
α
+
], and b
α
∈
[
b
α
-
,
b
α
+
], the following sets are set up by (11)
S
-
=
x
1
α
,
x
2
α
:
A
1
α
+
×
x
1
α
x
1
α
,
x
2
α
+
A
2
α
+
×
x
2
α
≤
b
α
-
,
x
1
α
,
x
2
α
x
1
α
≥
0
,
x
2
α
≥
0
x
1
α
,
x
2
α
:
A
1
α
+
,
S
+
=
x
1
α
,
x
2
α
:
A
1
α
-
×
x
1
α
x
1
α
,
x
2
α
+
A
2
α
-
×
x
2
α
≤
b
α
+
,
x
1
α
,
x
2
α
x
1
α
≥
0
,
x
2
α
≥
0
x
1
α
,
x
2
α
:
A
1
α
-
.Then we have S
-
⊆
S
+.Here we assume thatS
- and S
+ are nonempty polyhedrons.Theorem 7.
For anyα
∈
[
0,1
], if (
(
x
1
)
α
*
,
(
x
2
)
α
*
) is an optimal solution and F
α
* is corresponding objective function value of problem (10), then one has F
α
*
-
≤
F
α
*
≤
F
α
*
+, where F
α
*
- and F
α
*
+ are the lower and upper bounds of the upper level objective function of problem (7).Proof.
For fixed(
x
1
)
α
≥
0, denote the largest and smallest possible feasible regions of the lower level problem by (12)
S
-
x
1
α
=
x
2
α
∣
A
2
α
+
×
x
2
α
≤
b
α
-
-
A
1
α
+
×
x
1
α
,
x
2
α
≥
0
A
2
α
+
,
S
+
x
1
α
=
x
2
α
∣
A
2
α
-
×
x
2
α
≤
b
α
+
-
A
1
α
-
×
x
1
α
,
x
2
α
≥
0
A
2
α
-
.It is true that S
-
(
(
x
1
)
α
)
⊂
S
+
(
(
x
1
)
α
).
Denote the two solution sets of the lower level problem by(13)
Ψ
-
x
1
α
=
argmax
f
x
1
α
,
x
2
α
:
x
2
α
∈
S
-
x
1
α
,
Ψ
+
x
1
α
=
argmax
f
x
1
α
,
x
2
α
:
x
2
α
∈
S
+
x
1
α
,where f
(
(
x
1
)
α
,
(
x
2
)
α
)
=
(
c
22
)
α
±
⊗
(
x
2
)
α.
The inducible regions corresponding to the smallest and largest possible feasible regions are(14)
I
R
-
=
x
1
α
,
x
2
α
∈
S
-
,
x
2
α
∈
Ψ
-
x
1
α
,
I
R
+
=
x
1
α
,
x
2
α
∈
S
+
,
x
2
α
∈
Ψ
+
x
1
α
.
Therefore, the lower and upper bounds of the upper level objective function of problem (7) are (15)
F
α
*
-
=
max
⁡
F
-
x
1
α
,
x
2
α
∣
x
1
α
,
x
2
α
∈
I
R
-
,
F
α
*
+
=
max
⁡
F
+
x
1
α
,
x
2
α
∣
x
1
α
,
x
2
α
∈
I
R
+such that F
α
*
-
≤
F
α
*
+, and the proof is completed.
Theorem7 gives the optimal bounds of the interval bilevel programming problem (7).Definition 8.
A general interval linear programming model can be expressed as follows:(16)
max
⁡
f
±
=
c
±
x
±
s
.
t
.
A
±
x
±
≤
b
±
,
x
±
≥
0
,where A
±
∈
{
R
±
}
m
×
n, b
±
∈
{
R
±
}
m
×
1, c
±
∈
{
R
±
}
1
×
n, x
±
∈
{
R
±
}
n
×
1, and R
± denotes a set of interval numbers. According to Theorems (
1
) and (
2
) in [22], the model has the optimal objective function value and the optimal solutions as follows: f
opt
±
=
[
f
opt
-
,
f
opt
+
], x
j
opt
±
=
[
x
j
opt
-
,
x
j
opt
+
], x
j
opt
+
≥
x
j
opt
-, for all j.Next we discuss how to obtain solutions for the upper and lower bounds of the upper level objective function values of problem (7).For given(
x
1
)
α
±, the lower level problem of problem (7) can be written as(17)
max
⁡
f
α
±
=
∑
k
2
=
1
n
2
‍
c
22
k
2
α
±
⊗
x
2
k
2
α
±
s
.
t
.
∑
k
2
=
1
n
1
a
2
s
k
2
α
±
⊗
x
2
k
2
α
±
≤
b
s
α
±
⊖
∑
k
1
=
1
n
1
a
1
s
k
1
α
±
⊗
x
1
k
1
α
±
,
s
=
1,2
,
…
,
m
,
x
2
k
2
α
±
≥
0
,
k
2
=
1,2
,
…
,
n
2
.For the coefficientc
~
22 of problem (6), let the former q elements be positive and the latter (
n
2
-
q
) elements negative. According to Lemma 2 [15], for any α
∈
[
0,1
], the lower and upper bounds of the objective function of problem (17) can be expressed as (18)
f
α
-
=
∑
k
2
=
1
q
‍
c
22
k
2
α
-
×
x
2
k
2
α
-
+
∑
k
2
=
q
+
1
n
2
c
22
k
2
α
-
×
x
2
k
2
α
+
,
f
α
+
=
∑
k
2
=
1
q
c
22
k
2
α
+
×
x
2
k
2
α
+
+
∑
k
2
=
q
+
1
n
2
c
22
k
2
α
+
×
x
2
k
2
α
-
.For simplicity, denote the term(
b
s
)
α
±
⊖
∑
k
1
=
1
n
1
‍
(
a
1
s
k
1
)
α
±
⊗
(
x
1
k
1
)
α
± in the constraints of problem (17) by (
B
s
)
α
±.According to the robust two-step method [22], a submodel corresponding to f
α
- is firstly formulated and solved, and then the second submodel corresponding to f
α
+ can be formulated based on the solution of the first one. In detail, the submodel corresponding to f
α
-, which provides the first step of the solution process, can be formulated as(19)
max
⁡
f
α
-
=
∑
k
2
=
1
q
‍
c
22
k
2
α
-
×
x
2
k
2
α
-
max
⁡
+
∑
k
2
=
q
+
1
n
2
c
22
k
2
α
-
×
x
2
k
2
α
+
s
.
t
.
∑
k
2
=
1
q
‍
a
2
s
k
2
α
+
Sign
a
2
s
k
2
α
±
x
2
k
2
α
-
max
⁡
+
∑
k
2
=
q
+
1
n
2
‍
a
2
s
k
2
α
-
Sign
a
2
s
k
2
α
±
x
2
k
2
α
+
max
⁡
≤
B
s
α
-
,
s
=
1,2
,
…
,
m
,
max
⁡
x
2
k
2
α
-
≥
0
,
k
2
=
1,2
,
…
,
q
,
max
⁡
x
2
k
2
α
+
≥
0
,
k
2
=
q
+
1
,
k
2
+
2
,
…
,
n
2
.From submodel (19), solutions of (
x
2
k
2
*
)
α
-, k
2
=
1,2
,
…
,
q, and (
x
2
k
2
*
)
α
+, k
2
=
q
+
1
,
k
2
+
2
,
…
,
n
2, can be obtained. Denote the solution sets of model (19) by Ψ
-
(
(
x
1
)
α
).Based on the solutions of submodel (19), the submodel corresponding to f
α
+, which provides the second step of the solution process, can be formulated as follows:(20)
max
⁡
f
α
+
=
∑
k
2
=
1
q
‍
c
22
k
2
α
+
×
x
2
k
2
α
+
m
a
x
+
∑
k
2
=
q
+
1
n
2
‍
c
22
k
2
α
+
×
x
2
k
2
α
-
s
.
t
.
∑
k
2
=
1
q
‍
a
2
s
k
2
α
-
Sign
a
2
s
k
2
α
±
x
2
k
2
α
+
max
⁡
+
∑
k
2
=
q
+
1
n
2
‍
a
2
s
k
2
α
+
Sign
a
2
s
k
2
α
±
x
2
k
2
α
-
≤
B
s
α
+
,
max
⁡
s
=
1,2
,
…
,
m
,
max
⁡
∑
k
2
=
1
l
1
‍
a
2
s
k
2
α
-
x
2
k
2
α
+
+
∑
k
2
=
l
1
+
1
q
‍
a
2
s
k
2
α
-
x
2
k
2
*
α
-
max
⁡
+
∑
k
2
=
q
+
1
l
2
‍
a
2
s
k
2
α
-
x
2
k
2
α
-
max
⁡
+
∑
k
2
=
l
2
+
1
n
2
‍
a
2
s
k
2
α
-
x
2
k
2
*
α
-
≤
B
s
α
+
,
max
⁡
x
2
k
2
α
+
≥
x
2
k
2
*
α
-
,
x
2
k
2
α
+
≥
0
,
max
⁡
k
2
=
1,2
,
…
,
q
,
max
⁡
x
2
k
2
α
-
≤
x
2
k
2
*
α
+
,
x
2
k
2
α
-
≥
0
,
max
⁡
k
2
=
q
+
1
,
k
2
+
2
,
…
,
n
2
,where (
a
2
s
k
2
)
α
±
≥
0
(
k
2
=
1,2
,
…
,
l
1
;
k
2
=
l
2
+
1
,
l
2
+
2
,
…
,
n
2
) and (
a
2
s
k
2
)
α
±
≤
0
(
k
2
=
l
1
+
1
,
l
1
+
2
,
…
,
l
2
), where l
1
≤
q and l
2
≥
q.Solutions of(
x
2
k
2
*
)
α
+
≥
0, k
2
=
1,2
,
…
,
q, and (
x
2
k
2
*
)
α
-
≥
0, k
2
=
q
+
1
,
k
2
+
2
,
…
,
n
2, can be obtained by solving submodel (20). Denote the solution sets of model (20) by Ψ
+
(
(
x
1
)
α
).For the coefficientc
~
11 of problem (6), the former p elements are assumed to be positive and the latter (
n
1
-
p
) elements are negative. For the coefficient c
~
12, let the former q elements be positive and the latter (
n
2
-
q
) elements negative. Thus, for any α
∈
[
0,1
], the lower and upper bounds of the upper level objective function of problem (7) can be expressed as (21)
F
α
-
=
∑
k
1
=
1
p
‍
c
11
k
1
α
-
×
x
1
k
1
α
-
+
∑
k
1
=
p
+
1
n
1
c
11
k
1
α
-
×
x
1
k
1
α
+
+
∑
k
2
=
1
q
c
12
k
2
α
-
×
x
2
k
2
α
-
+
∑
k
2
=
q
+
1
n
2
c
12
k
2
α
-
×
x
2
k
2
α
+
,
F
α
+
=
∑
k
1
=
1
p
c
11
k
1
α
+
×
x
1
k
1
α
+
+
∑
k
1
=
p
+
1
n
1
c
11
k
1
α
+
×
x
1
k
1
α
-
+
∑
k
2
=
1
q
c
12
k
2
α
+
×
x
2
k
2
α
+
+
∑
k
2
=
q
+
1
n
2
c
12
k
2
α
+
×
x
2
k
2
α
-
.Thus the first subproblem of problem (7) that would correspond to F
α
- can be written as(22)
max
⁡
F
α
-
=
∑
k
1
=
1
p
‍
c
11
k
1
α
-
×
x
1
k
1
α
-
+
∑
k
1
=
p
+
1
n
1
‍
c
11
k
1
α
-
×
x
1
k
1
α
+
+
∑
k
2
=
1
q
‍
c
12
k
2
α
-
×
x
2
k
2
α
-
+
∑
k
2
=
q
+
1
n
2
‍
c
12
k
2
α
-
×
x
2
k
2
α
+
s
.
t
.
x
1
α
,
x
2
α
∈
S
-
,
x
2
α
∈
Ψ
-
x
1
α
,and the second subproblem of problem (7) that would correspond to F
α
+ can be written as(23)
max
⁡
F
α
+
=
∑
k
1
=
1
p
‍
c
11
k
1
α
+
×
x
1
k
1
α
+
m
a
x
+
∑
k
1
=
p
+
1
n
1
c
11
k
1
α
+
×
x
1
k
1
α
-
m
a
x
+
∑
k
2
=
1
q
c
12
k
2
α
+
×
x
2
k
2
α
+
m
a
x
+
∑
k
2
=
q
+
1
n
2
c
12
k
2
α
+
×
x
2
k
2
α
-
s
.
t
.
x
1
α
,
x
2
α
∈
S
+
,
x
2
α
∈
Ψ
+
x
1
α
.Based on the above analysis, problem (7) can be transformed into two deterministic subproblems (22) and (23) that correspond to the lower and upper bounds of the upper level objective function. Then, the solutions of problem (7) can be obtained through solving the two subproblems sequentially. Problem (22) will be solved firstly; then problem (23) will be derived and solved based on the solutions of submodel (22).IfΨ
-
(
(
x
1
)
α
) and Ψ
+
(
(
x
1
)
α
) are not a singleton for each (
x
1
)
α, we will consider here optimistic formulation of a bilevel programming problem. For details on the optimistic solution approach see [4].Furthermore, problems (22) and (23) can be rewritten as(24)
max
⁡
F
α
-
=
∑
k
1
=
1
p
c
11
k
1
α
-
×
x
1
k
1
α
-
max
⁡
+
∑
k
1
=
p
+
1
n
1
c
11
k
1
α
-
×
x
1
k
1
α
+
max
⁡
+
∑
k
2
=
1
q
‍
c
12
k
2
α
-
×
x
2
k
2
α
-
max
⁡
+
∑
k
2
=
q
+
1
n
2
c
12
k
2
α
-
×
x
2
k
2
α
+
max
⁡
f
α
-
=
∑
k
2
=
1
q
c
22
k
2
α
-
×
x
2
k
2
α
-
max
⁡
+
∑
k
2
=
q
+
1
n
2
c
22
k
2
α
-
×
x
2
k
2
α
+
s
.
t
.
∑
k
1
=
1
p
‍
a
1
s
k
1
α
+
Sign
a
1
s
k
1
α
±
x
1
k
1
α
-
max
⁡
+
∑
k
1
=
p
+
1
n
1
‍
a
1
s
k
1
α
-
Sign
a
s
1
k
1
α
±
x
1
k
1
α
+
max
⁡
+
∑
k
2
=
1
q
‍
a
2
s
k
2
α
+
Sign
a
2
s
k
2
α
±
x
2
k
2
α
-
max
⁡
+
∑
k
2
=
q
+
1
n
2
‍
a
2
s
k
2
α
-
Sign
a
2
s
k
2
α
±
x
2
k
2
α
+
max
⁡
≤
b
s
α
-
,
s
=
1,2
,
…
,
m
,
max
⁡
x
1
k
1
α
-
≥
0
,
k
1
=
1,2
,
…
,
p
,
max
⁡
x
1
k
1
α
+
≥
0
,
k
1
=
p
+
1
,
p
+
2
,
…
,
n
1
,
max
⁡
x
2
k
2
α
-
≥
0
,
k
2
=
1,2
,
…
,
q
,
max
⁡
x
2
k
2
α
+
≥
0
,
k
2
=
q
+
1
,
q
+
2
,
…
,
n
2
,
(25)
max
⁡
F
α
+
=
∑
k
1
=
1
p
‍
c
11
k
1
α
+
×
x
1
k
1
α
+
max
⁡
+
∑
k
1
=
p
+
1
n
1
c
11
k
1
α
+
×
x
1
k
1
α
-
max
⁡
+
∑
k
2
=
1
q
‍
c
12
k
2
α
+
×
x
2
k
2
α
+
max
⁡
+
∑
k
2
=
q
+
1
n
2
‍
c
12
k
2
α
+
×
x
2
k
2
α
-
max
⁡
f
α
+
=
∑
k
2
=
1
q
‍
c
22
k
2
α
+
×
x
2
k
2
α
+
max
⁡
+
∑
k
2
=
q
+
1
n
2
‍
c
22
k
2
α
+
×
x
2
k
2
α
-
s
.
t
.
∑
k
1
=
1
p
‍
a
s
1
k
1
α
-
Sign
a
1
s
k
1
α
±
x
1
k
1
α
+
max
⁡
+
∑
k
1
=
p
+
1
n
1
‍
a
1
s
k
1
α
+
Sign
a
1
s
k
1
α
±
x
1
k
1
α
-
max
⁡
+
∑
k
2
=
1
q
‍
a
2
s
k
2
α
-
Sign
a
2
s
k
2
α
±
x
2
k
2
α
+
max
⁡
+
∑
k
2
=
q
+
1
n
2
‍
a
2
s
k
2
α
+
Sign
a
2
s
k
2
α
±
x
2
k
2
α
-
max
⁡
≤
b
s
α
+
,
s
=
1,2
,
…
,
m
,
max
⁡
∑
k
1
=
1
i
1
‍
a
s
1
k
1
α
-
x
1
k
1
α
+
+
∑
k
1
=
i
1
+
1
p
‍
a
s
1
k
1
α
-
x
1
k
1
*
α
-
max
⁡
+
∑
k
1
=
p
+
1
i
2
‍
a
1
s
k
1
α
-
x
1
k
1
α
-
max
⁡
+
∑
k
1
=
i
2
+
1
n
2
‍
a
1
s
k
1
α
-
x
1
k
1
*
α
-
+
∑
k
2
=
1
l
1
a
2
s
k
2
α
-
x
2
k
2
α
+
max
⁡
+
∑
k
2
=
l
1
+
1
q
‍
a
2
s
k
2
α
-
x
2
k
2
*
α
-
max
⁡
+
∑
k
2
=
q
+
1
l
2
‍
a
2
s
k
2
-
x
2
k
2
α
-
max
⁡
+
∑
k
2
=
l
2
+
1
n
2
‍
a
2
s
k
2
-
x
2
k
2
*
α
-
max
⁡
≤
b
s
α
+
,
s
=
1,2
,
…
,
m
,
max
⁡
x
1
k
1
α
+
≥
x
1
k
1
*
α
-
,
x
1
k
1
α
+
≥
0
,
k
1
=
1,2
,
…
,
p
,
max
⁡
x
1
k
1
α
-
≤
x
1
k
1
*
α
+
,
x
1
k
1
α
-
≥
0
,
max
⁡
k
1
=
p
+
1
,
k
1
+
2
,
…
,
n
1
,
max
⁡
x
2
k
2
α
+
≥
x
2
k
2
*
α
-
,
x
2
k
2
α
+
≥
0
,
k
2
=
1,2
,
…
,
q
,
max
⁡
x
2
k
2
α
-
≤
x
2
k
2
*
α
+
,
x
2
k
2
α
-
≥
0
,
max
⁡
k
2
=
q
+
1
,
k
2
+
2
,
…
,
n
2
,where (
a
1
s
k
1
)
α
±
≥
0
(
k
1
=
1,2
,
…
,
i
1
;
k
1
=
i
2
+
1
,
i
2
+
2
,
…
,
n
1
) and (
a
1
s
k
1
)
α
±
≤
0
(
k
1
=
i
1
+
1
,
i
1
+
2
,
…
,
i
2
), where i
1
≤
p and i
2
≥
p; (
a
2
s
k
2
)
α
±
≥
0
(
k
2
=
1,2
,
…
,
l
1
;
k
2
=
l
2
+
1
,
l
2
+
2
,
…
,
n
2
) and (
a
2
s
k
2
)
α
±
≤
0
(
k
2
=
l
1
+
1
,
l
1
+
2
,
…
,
l
2
), where l
1
≤
q and l
2
≥
q.Thus solutions of(
x
1
k
1
*
)
α
-, k
1
=
1,2
,
…
,
p, (
x
1
k
1
*
)
α
+, k
1
=
p
+
1
,
p
+
2
,
…
,
n
1, (
x
2
k
2
*
)
α
-
,
k
2
=
1,2
,
…
,
q, and (
x
2
k
2
*
)
α
+
,
k
2
=
q
+
1
,
q
+
2
,
…
,
n
2, can be obtained from problem (24), whereas (
x
1
k
1
*
)
α
+
,
k
1
=
1,2
,
…
,
p, (
x
1
k
1
*
)
α
-
,
k
1
=
p
+
1
,
p
+
2
,
…
,
n
1, (
x
2
k
2
*
)
α
+
,
k
2
=
1,2
,
…
,
q, and (
x
2
k
2
*
)
α
-
,
k
2
=
q
+
1
,
q
+
2
,
…
,
n
2, can be obtained by solving problem (25).It is noted here that problems (24) and (25) are classic bilevel linear programming problems. There already have been some methods for solving this class of problems, like methods based on vertex enumeration and metaheuristics. In this study, the Kth-best algorithm which is proposed by Bialas and Karwan [27] is applied to solve the above two deterministic bilevel linear programming problems. The Kth-best algorithm for bilevel linear programming aims to find a global optimum solution by searching extreme points on the constraint region. The main idea of the algorithm is the extreme-point ranking according to the objective function of the upper level. To be more specific, the present best extreme point with respect to the upper level objective function is chosen to test if it is a point of the inducible region. If it is so, the current extreme point is the optimal solution. Otherwise, the next one will be selected and checked.By setting differentα-level sets, different lower and upper bounds of the upper level objective function of problem (7) can be generated by solving the above pair of problems (24) and (25).


### 3.2. Solution Algorithm

Due to the existence of fuzzy coefficients and fuzzy decision variables, it is natural to consider the optimal value of the fully fuzzy bilevel optimization problem (6) as a fuzzy number. In order to solve problem (6), we first discretize the range of membership grade [
0,1
] into a finite number of α-level sets. Let α
1
,
α
2
,
…
,
α
n be different level sets satisfying α
1
≤
α
2
≤
⋯
≤
α
n. Based on models (24) and (25), a series of lower and upper bounds of the upper level objective function of problem (7) can be obtained under each α-level set. In practice, fuzzy numbers with simple membership functions are often preferred. By using α
1
,
α
2
,
…
,
α
n-level sets, the linear piecewise trapezoidal fuzzy number is introduced to approximate the optimal value of the upper level objective function of problem (6). To be more specific, the optimal value of the upper level objective function of problem (6) is characterized by the following piecewise trapezoidal membership function: (26)
μ
F
~
*
(
t
)
=
0
t
<
F
α
1
*
-
,
α
2
-
α
1
F
α
2
*
-
-
F
α
1
*
-
(
t
-
F
α
1
*
-
)
+
α
1
F
α
1
*
-
≤
t
<
F
α
2
*
-
,
α
3
-
α
2
F
α
3
*
-
-
F
α
2
*
-
(
t
-
F
α
2
*
-
)
+
α
2
F
α
2
*
-
≤
t
<
F
α
3
*
-
,
⋮
⋮
α
n
F
α
n
*
-
≤
t
<
F
α
n
*
+
,
⋮
⋮
α
2
-
α
1
F
α
2
*
+
-
F
α
1
*
+
(
t
-
F
α
1
*
+
)
+
α
1
F
α
2
*
+
≤
t
<
F
α
1
*
-
,
0
t
≥
F
α
1
*
+
.On the other hand, a series of optimal solutions of problem (7) corresponding to the lower and upper bounds of its objective function can be also generated by depending on different level sets. Based on statistical regression method, we can approximately obtain the membership function for every decision variable of problem (6). Specifically, each α-level set is input data, and the corresponding lower and upper bounds of decision variables are output data. In this way, the membership function for decision variables can be obtained.The detailed solution process for problem (6) can be summarized as follows.Step 1.
Discretize the range of membership grade[
0,1
] into a set of α-level sets (i.e., α
1
,
α
2
,
…
,
α
t) such that 0
≤
α
1
<
α
2
<
⋯
<
α
t
≤
1.Step 2.
Transform problem (6) into an interval bilevel linear programming problem under each α-level set. Based on models (24) and (25), the interval bilevel linear programming problem can be converted into two deterministic subproblems.Step 3.
Based on theKth-best algorithm, the submodel corresponding to F
α
- is to be solved firstly, and then the submodel corresponding to F
α
+ is solved based on solutions from the first submodel.Step 4.
The optimal values of the upper level objective function of problem (6) can be approximated by the linear piecewise trapezoidal fuzzy number. By statistical regression, the membership function for every decision variable can be obtained.


## 3.1. Modeling Formulation

Observing that all the coefficients and decision variables of the upper level objective function of problem (6) are fuzzy numbers, the upper level objective function is also a fuzzy number. It is well known that fuzzy numbers can be defined by the families of their α-level sets according to the decomposition principle [26]. Then the optimal value of the upper level objective function of problem (6) can be expressed as the families of its α-level sets.Based on this fact, we first discretize membership grade of fuzzy coefficients and fuzzy decision variables of problem (6) into a finite number of α-level sets. For any α
∈
[
0,1
], the α-level sets of x
~
j
k
j, c
~
1
j
k
j, j
=
1,2, k
j
=
1,2
,
…
,
n
j, c
~
22
k
2, a
~
j
s
t
j, and b
~
s, s
=
1,2
,
…
,
m, t
j
=
1,2
,
…
,
n
j, can be denoted as (
x
~
j
k
j
)
α
=
[
(
x
j
k
j
)
α
-
,
(
x
j
k
j
)
α
+
], (
c
~
1
j
k
j
)
α
=
[
(
c
1
j
k
j
)
α
-
,
(
c
1
j
k
j
)
α
+
], (
c
~
22
k
2
)
α
=
[
(
c
22
k
2
)
α
-
,
(
c
22
k
2
)
α
+
], (
a
~
j
s
t
j
)
α
=
[
(
a
j
s
t
j
)
α
-
,
(
a
j
s
t
j
)
α
+
], and (
b
~
s
)
α
=
[
(
b
s
)
α
-
,
(
b
s
)
α
+
].Considering that theα-level sets of fuzzy numbers are actually closed intervals, the operations on fuzzy numbers are indeed performed by the interval arithmetic operations for α-level sets. Then the fully fuzzy bilevel linear programming problem (6) can be transformed into the following interval bilevel linear programming problem for any α-level set:(7)
max
⁡
F
α
±
=
∑
k
1
=
1
n
1
‍
c
11
k
1
α
±
⊗
x
1
k
1
α
±
max
⁡
⊕
∑
k
2
=
1
n
2
c
12
k
2
α
±
⊗
x
2
k
2
α
±
max
⁡
f
α
±
=
∑
k
2
=
1
n
2
‍
c
22
k
2
α
±
⊗
x
2
k
2
α
±
s
.
t
.
∑
k
1
=
1
n
1
‍
a
1
s
k
1
α
±
⊗
x
1
k
1
α
±
max
⁡
⊕
∑
k
2
=
1
n
1
a
2
s
k
2
α
±
⊗
x
2
k
2
α
±
≤
b
s
α
±
,
max
⁡
s
=
1,2
,
…
,
m
,
max
⁡
x
1
k
1
α
±
≥
0
,
k
1
=
1,2
,
…
,
n
1
,
max
⁡
x
2
k
2
α
±
≥
0
,
k
2
=
1,2
,
…
,
n
2
.Remark 6.
For problem (6), the upper level objective function F
~ can be rewritten as ∑
k
1
=
1
n
1
‍
c
~
11
k
1
⊗
x
~
1
k
1
⊕
∑
k
2
=
1
n
2
‍
c
~
12
k
2
⊗
x
~
2
k
2. Then we have (
F
~
)
α
=
F
α
±
=
(
∑
k
1
=
1
n
1
‍
c
~
11
k
1
⊗
x
~
1
k
1
⊕
∑
k
2
=
1
n
2
‍
c
~
12
k
2
⊗
x
~
2
k
2
)
α
=
∑
k
1
=
1
n
1
‍
(
c
11
k
1
)
α
±
⊗
(
x
1
k
1
)
α
±
⊕
∑
k
2
=
1
n
2
‍
(
c
12
k
2
)
α
±
⊗
(
x
2
k
2
)
α
± for any α-level set. Obviously, the lower level objective function and the constraints of problem (7) can be obtained by similar algebraic operation.Under differentα-level sets, a series of interval bilevel linear programming problems are generated. Here we are interested in computing the lower and upper bounds of the upper level objective functions of these interval bilevel linear programming problems. Based on these results, the optimal value of the upper level objective function of problem (6) can be decomposed as (8)
F
~
*
=
⋃
α
∈
[
0,1
]
α
F
α
*
-
,
F
α
*
+
.Hence, we will discuss how to determine the lower and upper bounds of the upper level objective function of the interval bilevel programming problem (7) in the following section.Since all the coefficients and the decision variables of problem (7) are interval numbers, the optimal upper level objective function values and the feasible regions of the problem are directly affected by different specific values of the coefficients and the decision variables chosen from their ranges. To deal with problem (7), we analyze model characteristics and the interrelationships among the coefficients and the decision variables in both objective functions and the constraints.Clearly, the lower level problem of problem (7) is a conventional interval linear programming. Huang et al. [17] proposed the two-step method to solve this kind of problem. The basic idea of this method is to first transform the interval linear programming problem into two deterministic subproblems which correspond to the lower and upper bounds of the objective function value and then solve the two subproblems sequentially to obtain the solutions of the problem. However, this method may result in constraint violation in its solution space [22]. To avoid this, Fan and Huang [22] developed a robust two-step method for solving the interval linear programming problem. In this way, we discuss the lower and upper bounds of the objective function of the lower level problem and then give the optimal bounds of the upper level objective function of the interval bilevel linear programming problem (7).For simplicity, problem (7) can be rewritten as (9)
max
⁡
F
α
±
=
c
11
α
±
×
x
1
α
±
+
c
12
α
±
×
x
2
α
±
max
⁡
f
α
±
=
c
22
α
±
×
x
2
α
±
s
.
t
.
A
1
α
±
×
x
1
α
±
+
A
2
α
±
×
x
2
α
±
≤
b
α
±
,
x
1
α
±
≥
0
,
x
2
α
±
≥
0
,where (
c
1
j
)
α
±
=
(
(
c
1
j
1
)
α
±
,
(
c
1
j
2
)
α
±
,
…
,
(
c
1
j
n
j
)
α
±
), j
=
1,2, (
x
j
)
α
±
=
(
(
x
j
1
)
α
±
,
(
x
j
2
)
α
±
,
…
,
(
x
j
n
j
)
α
±
), (
c
22
)
α
±
=
(
(
c
221
)
α
±
,
(
c
222
)
α
±
,
…
,
(
c
22
n
2
)
α
±
), (
A
j
)
α
±
=
(
(
a
j
s
t
j
)
α
±
), and b
α
±
=
(
(
b
1
)
α
±
,
(
b
2
)
α
±
,
…
,
(
b
m
)
α
±
).We call the following problem a characteristic version of problem (7):(10)
max
⁡
F
α
=
c
11
α
×
x
1
α
+
c
12
α
×
x
2
α
max
⁡
f
α
=
c
22
α
×
x
2
α
s
.
t
.
A
1
α
×
x
1
α
+
A
2
α
×
x
2
α
≤
b
α
,
x
1
α
≥
0
,
x
2
α
≥
0
,where (
c
1
j
)
α
∈
[
(
c
1
j
)
α
-
,
(
c
1
j
)
α
+
], j
=
1,2, (
x
j
)
α
∈
[
(
x
j
)
α
-
,
(
x
j
)
α
+
], (
A
j
)
α
∈
[
(
A
j
)
α
-, (
A
j
)
α
+
], and b
α
∈
[
b
α
-
,
b
α
+
].For anyα
∈
[
0,1
], (
A
1
)
α
∈
[
(
A
1
)
α
-
,
(
A
1
)
α
+
], (
A
2
)
α
∈
[
(
A
2
)
α
-
,
(
A
2
)
α
+
], and b
α
∈
[
b
α
-
,
b
α
+
], the following sets are set up by (11)
S
-
=
x
1
α
,
x
2
α
:
A
1
α
+
×
x
1
α
x
1
α
,
x
2
α
+
A
2
α
+
×
x
2
α
≤
b
α
-
,
x
1
α
,
x
2
α
x
1
α
≥
0
,
x
2
α
≥
0
x
1
α
,
x
2
α
:
A
1
α
+
,
S
+
=
x
1
α
,
x
2
α
:
A
1
α
-
×
x
1
α
x
1
α
,
x
2
α
+
A
2
α
-
×
x
2
α
≤
b
α
+
,
x
1
α
,
x
2
α
x
1
α
≥
0
,
x
2
α
≥
0
x
1
α
,
x
2
α
:
A
1
α
-
.Then we have S
-
⊆
S
+.Here we assume thatS
- and S
+ are nonempty polyhedrons.Theorem 7.
For anyα
∈
[
0,1
], if (
(
x
1
)
α
*
,
(
x
2
)
α
*
) is an optimal solution and F
α
* is corresponding objective function value of problem (10), then one has F
α
*
-
≤
F
α
*
≤
F
α
*
+, where F
α
*
- and F
α
*
+ are the lower and upper bounds of the upper level objective function of problem (7).Proof.
For fixed(
x
1
)
α
≥
0, denote the largest and smallest possible feasible regions of the lower level problem by (12)
S
-
x
1
α
=
x
2
α
∣
A
2
α
+
×
x
2
α
≤
b
α
-
-
A
1
α
+
×
x
1
α
,
x
2
α
≥
0
A
2
α
+
,
S
+
x
1
α
=
x
2
α
∣
A
2
α
-
×
x
2
α
≤
b
α
+
-
A
1
α
-
×
x
1
α
,
x
2
α
≥
0
A
2
α
-
.It is true that S
-
(
(
x
1
)
α
)
⊂
S
+
(
(
x
1
)
α
).
Denote the two solution sets of the lower level problem by(13)
Ψ
-
x
1
α
=
argmax
f
x
1
α
,
x
2
α
:
x
2
α
∈
S
-
x
1
α
,
Ψ
+
x
1
α
=
argmax
f
x
1
α
,
x
2
α
:
x
2
α
∈
S
+
x
1
α
,where f
(
(
x
1
)
α
,
(
x
2
)
α
)
=
(
c
22
)
α
±
⊗
(
x
2
)
α.
The inducible regions corresponding to the smallest and largest possible feasible regions are(14)
I
R
-
=
x
1
α
,
x
2
α
∈
S
-
,
x
2
α
∈
Ψ
-
x
1
α
,
I
R
+
=
x
1
α
,
x
2
α
∈
S
+
,
x
2
α
∈
Ψ
+
x
1
α
.
Therefore, the lower and upper bounds of the upper level objective function of problem (7) are (15)
F
α
*
-
=
max
⁡
F
-
x
1
α
,
x
2
α
∣
x
1
α
,
x
2
α
∈
I
R
-
,
F
α
*
+
=
max
⁡
F
+
x
1
α
,
x
2
α
∣
x
1
α
,
x
2
α
∈
I
R
+such that F
α
*
-
≤
F
α
*
+, and the proof is completed.
Theorem7 gives the optimal bounds of the interval bilevel programming problem (7).Definition 8.
A general interval linear programming model can be expressed as follows:(16)
max
⁡
f
±
=
c
±
x
±
s
.
t
.
A
±
x
±
≤
b
±
,
x
±
≥
0
,where A
±
∈
{
R
±
}
m
×
n, b
±
∈
{
R
±
}
m
×
1, c
±
∈
{
R
±
}
1
×
n, x
±
∈
{
R
±
}
n
×
1, and R
± denotes a set of interval numbers. According to Theorems (
1
) and (
2
) in [22], the model has the optimal objective function value and the optimal solutions as follows: f
opt
±
=
[
f
opt
-
,
f
opt
+
], x
j
opt
±
=
[
x
j
opt
-
,
x
j
opt
+
], x
j
opt
+
≥
x
j
opt
-, for all j.Next we discuss how to obtain solutions for the upper and lower bounds of the upper level objective function values of problem (7).For given(
x
1
)
α
±, the lower level problem of problem (7) can be written as(17)
max
⁡
f
α
±
=
∑
k
2
=
1
n
2
‍
c
22
k
2
α
±
⊗
x
2
k
2
α
±
s
.
t
.
∑
k
2
=
1
n
1
a
2
s
k
2
α
±
⊗
x
2
k
2
α
±
≤
b
s
α
±
⊖
∑
k
1
=
1
n
1
a
1
s
k
1
α
±
⊗
x
1
k
1
α
±
,
s
=
1,2
,
…
,
m
,
x
2
k
2
α
±
≥
0
,
k
2
=
1,2
,
…
,
n
2
.For the coefficientc
~
22 of problem (6), let the former q elements be positive and the latter (
n
2
-
q
) elements negative. According to Lemma 2 [15], for any α
∈
[
0,1
], the lower and upper bounds of the objective function of problem (17) can be expressed as (18)
f
α
-
=
∑
k
2
=
1
q
‍
c
22
k
2
α
-
×
x
2
k
2
α
-
+
∑
k
2
=
q
+
1
n
2
c
22
k
2
α
-
×
x
2
k
2
α
+
,
f
α
+
=
∑
k
2
=
1
q
c
22
k
2
α
+
×
x
2
k
2
α
+
+
∑
k
2
=
q
+
1
n
2
c
22
k
2
α
+
×
x
2
k
2
α
-
.For simplicity, denote the term(
b
s
)
α
±
⊖
∑
k
1
=
1
n
1
‍
(
a
1
s
k
1
)
α
±
⊗
(
x
1
k
1
)
α
± in the constraints of problem (17) by (
B
s
)
α
±.According to the robust two-step method [22], a submodel corresponding to f
α
- is firstly formulated and solved, and then the second submodel corresponding to f
α
+ can be formulated based on the solution of the first one. In detail, the submodel corresponding to f
α
-, which provides the first step of the solution process, can be formulated as(19)
max
⁡
f
α
-
=
∑
k
2
=
1
q
‍
c
22
k
2
α
-
×
x
2
k
2
α
-
max
⁡
+
∑
k
2
=
q
+
1
n
2
c
22
k
2
α
-
×
x
2
k
2
α
+
s
.
t
.
∑
k
2
=
1
q
‍
a
2
s
k
2
α
+
Sign
a
2
s
k
2
α
±
x
2
k
2
α
-
max
⁡
+
∑
k
2
=
q
+
1
n
2
‍
a
2
s
k
2
α
-
Sign
a
2
s
k
2
α
±
x
2
k
2
α
+
max
⁡
≤
B
s
α
-
,
s
=
1,2
,
…
,
m
,
max
⁡
x
2
k
2
α
-
≥
0
,
k
2
=
1,2
,
…
,
q
,
max
⁡
x
2
k
2
α
+
≥
0
,
k
2
=
q
+
1
,
k
2
+
2
,
…
,
n
2
.From submodel (19), solutions of (
x
2
k
2
*
)
α
-, k
2
=
1,2
,
…
,
q, and (
x
2
k
2
*
)
α
+, k
2
=
q
+
1
,
k
2
+
2
,
…
,
n
2, can be obtained. Denote the solution sets of model (19) by Ψ
-
(
(
x
1
)
α
).Based on the solutions of submodel (19), the submodel corresponding to f
α
+, which provides the second step of the solution process, can be formulated as follows:(20)
max
⁡
f
α
+
=
∑
k
2
=
1
q
‍
c
22
k
2
α
+
×
x
2
k
2
α
+
m
a
x
+
∑
k
2
=
q
+
1
n
2
‍
c
22
k
2
α
+
×
x
2
k
2
α
-
s
.
t
.
∑
k
2
=
1
q
‍
a
2
s
k
2
α
-
Sign
a
2
s
k
2
α
±
x
2
k
2
α
+
max
⁡
+
∑
k
2
=
q
+
1
n
2
‍
a
2
s
k
2
α
+
Sign
a
2
s
k
2
α
±
x
2
k
2
α
-
≤
B
s
α
+
,
max
⁡
s
=
1,2
,
…
,
m
,
max
⁡
∑
k
2
=
1
l
1
‍
a
2
s
k
2
α
-
x
2
k
2
α
+
+
∑
k
2
=
l
1
+
1
q
‍
a
2
s
k
2
α
-
x
2
k
2
*
α
-
max
⁡
+
∑
k
2
=
q
+
1
l
2
‍
a
2
s
k
2
α
-
x
2
k
2
α
-
max
⁡
+
∑
k
2
=
l
2
+
1
n
2
‍
a
2
s
k
2
α
-
x
2
k
2
*
α
-
≤
B
s
α
+
,
max
⁡
x
2
k
2
α
+
≥
x
2
k
2
*
α
-
,
x
2
k
2
α
+
≥
0
,
max
⁡
k
2
=
1,2
,
…
,
q
,
max
⁡
x
2
k
2
α
-
≤
x
2
k
2
*
α
+
,
x
2
k
2
α
-
≥
0
,
max
⁡
k
2
=
q
+
1
,
k
2
+
2
,
…
,
n
2
,where (
a
2
s
k
2
)
α
±
≥
0
(
k
2
=
1,2
,
…
,
l
1
;
k
2
=
l
2
+
1
,
l
2
+
2
,
…
,
n
2
) and (
a
2
s
k
2
)
α
±
≤
0
(
k
2
=
l
1
+
1
,
l
1
+
2
,
…
,
l
2
), where l
1
≤
q and l
2
≥
q.Solutions of(
x
2
k
2
*
)
α
+
≥
0, k
2
=
1,2
,
…
,
q, and (
x
2
k
2
*
)
α
-
≥
0, k
2
=
q
+
1
,
k
2
+
2
,
…
,
n
2, can be obtained by solving submodel (20). Denote the solution sets of model (20) by Ψ
+
(
(
x
1
)
α
).For the coefficientc
~
11 of problem (6), the former p elements are assumed to be positive and the latter (
n
1
-
p
) elements are negative. For the coefficient c
~
12, let the former q elements be positive and the latter (
n
2
-
q
) elements negative. Thus, for any α
∈
[
0,1
], the lower and upper bounds of the upper level objective function of problem (7) can be expressed as (21)
F
α
-
=
∑
k
1
=
1
p
‍
c
11
k
1
α
-
×
x
1
k
1
α
-
+
∑
k
1
=
p
+
1
n
1
c
11
k
1
α
-
×
x
1
k
1
α
+
+
∑
k
2
=
1
q
c
12
k
2
α
-
×
x
2
k
2
α
-
+
∑
k
2
=
q
+
1
n
2
c
12
k
2
α
-
×
x
2
k
2
α
+
,
F
α
+
=
∑
k
1
=
1
p
c
11
k
1
α
+
×
x
1
k
1
α
+
+
∑
k
1
=
p
+
1
n
1
c
11
k
1
α
+
×
x
1
k
1
α
-
+
∑
k
2
=
1
q
c
12
k
2
α
+
×
x
2
k
2
α
+
+
∑
k
2
=
q
+
1
n
2
c
12
k
2
α
+
×
x
2
k
2
α
-
.Thus the first subproblem of problem (7) that would correspond to F
α
- can be written as(22)
max
⁡
F
α
-
=
∑
k
1
=
1
p
‍
c
11
k
1
α
-
×
x
1
k
1
α
-
+
∑
k
1
=
p
+
1
n
1
‍
c
11
k
1
α
-
×
x
1
k
1
α
+
+
∑
k
2
=
1
q
‍
c
12
k
2
α
-
×
x
2
k
2
α
-
+
∑
k
2
=
q
+
1
n
2
‍
c
12
k
2
α
-
×
x
2
k
2
α
+
s
.
t
.
x
1
α
,
x
2
α
∈
S
-
,
x
2
α
∈
Ψ
-
x
1
α
,and the second subproblem of problem (7) that would correspond to F
α
+ can be written as(23)
max
⁡
F
α
+
=
∑
k
1
=
1
p
‍
c
11
k
1
α
+
×
x
1
k
1
α
+
m
a
x
+
∑
k
1
=
p
+
1
n
1
c
11
k
1
α
+
×
x
1
k
1
α
-
m
a
x
+
∑
k
2
=
1
q
c
12
k
2
α
+
×
x
2
k
2
α
+
m
a
x
+
∑
k
2
=
q
+
1
n
2
c
12
k
2
α
+
×
x
2
k
2
α
-
s
.
t
.
x
1
α
,
x
2
α
∈
S
+
,
x
2
α
∈
Ψ
+
x
1
α
.Based on the above analysis, problem (7) can be transformed into two deterministic subproblems (22) and (23) that correspond to the lower and upper bounds of the upper level objective function. Then, the solutions of problem (7) can be obtained through solving the two subproblems sequentially. Problem (22) will be solved firstly; then problem (23) will be derived and solved based on the solutions of submodel (22).IfΨ
-
(
(
x
1
)
α
) and Ψ
+
(
(
x
1
)
α
) are not a singleton for each (
x
1
)
α, we will consider here optimistic formulation of a bilevel programming problem. For details on the optimistic solution approach see [4].Furthermore, problems (22) and (23) can be rewritten as(24)
max
⁡
F
α
-
=
∑
k
1
=
1
p
c
11
k
1
α
-
×
x
1
k
1
α
-
max
⁡
+
∑
k
1
=
p
+
1
n
1
c
11
k
1
α
-
×
x
1
k
1
α
+
max
⁡
+
∑
k
2
=
1
q
‍
c
12
k
2
α
-
×
x
2
k
2
α
-
max
⁡
+
∑
k
2
=
q
+
1
n
2
c
12
k
2
α
-
×
x
2
k
2
α
+
max
⁡
f
α
-
=
∑
k
2
=
1
q
c
22
k
2
α
-
×
x
2
k
2
α
-
max
⁡
+
∑
k
2
=
q
+
1
n
2
c
22
k
2
α
-
×
x
2
k
2
α
+
s
.
t
.
∑
k
1
=
1
p
‍
a
1
s
k
1
α
+
Sign
a
1
s
k
1
α
±
x
1
k
1
α
-
max
⁡
+
∑
k
1
=
p
+
1
n
1
‍
a
1
s
k
1
α
-
Sign
a
s
1
k
1
α
±
x
1
k
1
α
+
max
⁡
+
∑
k
2
=
1
q
‍
a
2
s
k
2
α
+
Sign
a
2
s
k
2
α
±
x
2
k
2
α
-
max
⁡
+
∑
k
2
=
q
+
1
n
2
‍
a
2
s
k
2
α
-
Sign
a
2
s
k
2
α
±
x
2
k
2
α
+
max
⁡
≤
b
s
α
-
,
s
=
1,2
,
…
,
m
,
max
⁡
x
1
k
1
α
-
≥
0
,
k
1
=
1,2
,
…
,
p
,
max
⁡
x
1
k
1
α
+
≥
0
,
k
1
=
p
+
1
,
p
+
2
,
…
,
n
1
,
max
⁡
x
2
k
2
α
-
≥
0
,
k
2
=
1,2
,
…
,
q
,
max
⁡
x
2
k
2
α
+
≥
0
,
k
2
=
q
+
1
,
q
+
2
,
…
,
n
2
,
(25)
max
⁡
F
α
+
=
∑
k
1
=
1
p
‍
c
11
k
1
α
+
×
x
1
k
1
α
+
max
⁡
+
∑
k
1
=
p
+
1
n
1
c
11
k
1
α
+
×
x
1
k
1
α
-
max
⁡
+
∑
k
2
=
1
q
‍
c
12
k
2
α
+
×
x
2
k
2
α
+
max
⁡
+
∑
k
2
=
q
+
1
n
2
‍
c
12
k
2
α
+
×
x
2
k
2
α
-
max
⁡
f
α
+
=
∑
k
2
=
1
q
‍
c
22
k
2
α
+
×
x
2
k
2
α
+
max
⁡
+
∑
k
2
=
q
+
1
n
2
‍
c
22
k
2
α
+
×
x
2
k
2
α
-
s
.
t
.
∑
k
1
=
1
p
‍
a
s
1
k
1
α
-
Sign
a
1
s
k
1
α
±
x
1
k
1
α
+
max
⁡
+
∑
k
1
=
p
+
1
n
1
‍
a
1
s
k
1
α
+
Sign
a
1
s
k
1
α
±
x
1
k
1
α
-
max
⁡
+
∑
k
2
=
1
q
‍
a
2
s
k
2
α
-
Sign
a
2
s
k
2
α
±
x
2
k
2
α
+
max
⁡
+
∑
k
2
=
q
+
1
n
2
‍
a
2
s
k
2
α
+
Sign
a
2
s
k
2
α
±
x
2
k
2
α
-
max
⁡
≤
b
s
α
+
,
s
=
1,2
,
…
,
m
,
max
⁡
∑
k
1
=
1
i
1
‍
a
s
1
k
1
α
-
x
1
k
1
α
+
+
∑
k
1
=
i
1
+
1
p
‍
a
s
1
k
1
α
-
x
1
k
1
*
α
-
max
⁡
+
∑
k
1
=
p
+
1
i
2
‍
a
1
s
k
1
α
-
x
1
k
1
α
-
max
⁡
+
∑
k
1
=
i
2
+
1
n
2
‍
a
1
s
k
1
α
-
x
1
k
1
*
α
-
+
∑
k
2
=
1
l
1
a
2
s
k
2
α
-
x
2
k
2
α
+
max
⁡
+
∑
k
2
=
l
1
+
1
q
‍
a
2
s
k
2
α
-
x
2
k
2
*
α
-
max
⁡
+
∑
k
2
=
q
+
1
l
2
‍
a
2
s
k
2
-
x
2
k
2
α
-
max
⁡
+
∑
k
2
=
l
2
+
1
n
2
‍
a
2
s
k
2
-
x
2
k
2
*
α
-
max
⁡
≤
b
s
α
+
,
s
=
1,2
,
…
,
m
,
max
⁡
x
1
k
1
α
+
≥
x
1
k
1
*
α
-
,
x
1
k
1
α
+
≥
0
,
k
1
=
1,2
,
…
,
p
,
max
⁡
x
1
k
1
α
-
≤
x
1
k
1
*
α
+
,
x
1
k
1
α
-
≥
0
,
max
⁡
k
1
=
p
+
1
,
k
1
+
2
,
…
,
n
1
,
max
⁡
x
2
k
2
α
+
≥
x
2
k
2
*
α
-
,
x
2
k
2
α
+
≥
0
,
k
2
=
1,2
,
…
,
q
,
max
⁡
x
2
k
2
α
-
≤
x
2
k
2
*
α
+
,
x
2
k
2
α
-
≥
0
,
max
⁡
k
2
=
q
+
1
,
k
2
+
2
,
…
,
n
2
,where (
a
1
s
k
1
)
α
±
≥
0
(
k
1
=
1,2
,
…
,
i
1
;
k
1
=
i
2
+
1
,
i
2
+
2
,
…
,
n
1
) and (
a
1
s
k
1
)
α
±
≤
0
(
k
1
=
i
1
+
1
,
i
1
+
2
,
…
,
i
2
), where i
1
≤
p and i
2
≥
p; (
a
2
s
k
2
)
α
±
≥
0
(
k
2
=
1,2
,
…
,
l
1
;
k
2
=
l
2
+
1
,
l
2
+
2
,
…
,
n
2
) and (
a
2
s
k
2
)
α
±
≤
0
(
k
2
=
l
1
+
1
,
l
1
+
2
,
…
,
l
2
), where l
1
≤
q and l
2
≥
q.Thus solutions of(
x
1
k
1
*
)
α
-, k
1
=
1,2
,
…
,
p, (
x
1
k
1
*
)
α
+, k
1
=
p
+
1
,
p
+
2
,
…
,
n
1, (
x
2
k
2
*
)
α
-
,
k
2
=
1,2
,
…
,
q, and (
x
2
k
2
*
)
α
+
,
k
2
=
q
+
1
,
q
+
2
,
…
,
n
2, can be obtained from problem (24), whereas (
x
1
k
1
*
)
α
+
,
k
1
=
1,2
,
…
,
p, (
x
1
k
1
*
)
α
-
,
k
1
=
p
+
1
,
p
+
2
,
…
,
n
1, (
x
2
k
2
*
)
α
+
,
k
2
=
1,2
,
…
,
q, and (
x
2
k
2
*
)
α
-
,
k
2
=
q
+
1
,
q
+
2
,
…
,
n
2, can be obtained by solving problem (25).It is noted here that problems (24) and (25) are classic bilevel linear programming problems. There already have been some methods for solving this class of problems, like methods based on vertex enumeration and metaheuristics. In this study, the Kth-best algorithm which is proposed by Bialas and Karwan [27] is applied to solve the above two deterministic bilevel linear programming problems. The Kth-best algorithm for bilevel linear programming aims to find a global optimum solution by searching extreme points on the constraint region. The main idea of the algorithm is the extreme-point ranking according to the objective function of the upper level. To be more specific, the present best extreme point with respect to the upper level objective function is chosen to test if it is a point of the inducible region. If it is so, the current extreme point is the optimal solution. Otherwise, the next one will be selected and checked.By setting differentα-level sets, different lower and upper bounds of the upper level objective function of problem (7) can be generated by solving the above pair of problems (24) and (25).


## 3.2. Solution Algorithm

Due to the existence of fuzzy coefficients and fuzzy decision variables, it is natural to consider the optimal value of the fully fuzzy bilevel optimization problem (6) as a fuzzy number. In order to solve problem (6), we first discretize the range of membership grade [
0,1
] into a finite number of α-level sets. Let α
1
,
α
2
,
…
,
α
n be different level sets satisfying α
1
≤
α
2
≤
⋯
≤
α
n. Based on models (24) and (25), a series of lower and upper bounds of the upper level objective function of problem (7) can be obtained under each α-level set. In practice, fuzzy numbers with simple membership functions are often preferred. By using α
1
,
α
2
,
…
,
α
n-level sets, the linear piecewise trapezoidal fuzzy number is introduced to approximate the optimal value of the upper level objective function of problem (6). To be more specific, the optimal value of the upper level objective function of problem (6) is characterized by the following piecewise trapezoidal membership function: (26)
μ
F
~
*
(
t
)
=
0
t
<
F
α
1
*
-
,
α
2
-
α
1
F
α
2
*
-
-
F
α
1
*
-
(
t
-
F
α
1
*
-
)
+
α
1
F
α
1
*
-
≤
t
<
F
α
2
*
-
,
α
3
-
α
2
F
α
3
*
-
-
F
α
2
*
-
(
t
-
F
α
2
*
-
)
+
α
2
F
α
2
*
-
≤
t
<
F
α
3
*
-
,
⋮
⋮
α
n
F
α
n
*
-
≤
t
<
F
α
n
*
+
,
⋮
⋮
α
2
-
α
1
F
α
2
*
+
-
F
α
1
*
+
(
t
-
F
α
1
*
+
)
+
α
1
F
α
2
*
+
≤
t
<
F
α
1
*
-
,
0
t
≥
F
α
1
*
+
.On the other hand, a series of optimal solutions of problem (7) corresponding to the lower and upper bounds of its objective function can be also generated by depending on different level sets. Based on statistical regression method, we can approximately obtain the membership function for every decision variable of problem (6). Specifically, each α-level set is input data, and the corresponding lower and upper bounds of decision variables are output data. In this way, the membership function for decision variables can be obtained.The detailed solution process for problem (6) can be summarized as follows.Step 1.
Discretize the range of membership grade[
0,1
] into a set of α-level sets (i.e., α
1
,
α
2
,
…
,
α
t) such that 0
≤
α
1
<
α
2
<
⋯
<
α
t
≤
1.Step 2.
Transform problem (6) into an interval bilevel linear programming problem under each α-level set. Based on models (24) and (25), the interval bilevel linear programming problem can be converted into two deterministic subproblems.Step 3.
Based on theKth-best algorithm, the submodel corresponding to F
α
- is to be solved firstly, and then the submodel corresponding to F
α
+ is solved based on solutions from the first submodel.Step 4.
The optimal values of the upper level objective function of problem (6) can be approximated by the linear piecewise trapezoidal fuzzy number. By statistical regression, the membership function for every decision variable can be obtained.


## 4. Numerical Example and Analysis

### 4.1. Numerical Example

In this section, a numerical example is given to illustrate the proposed approach. Consider the following bilevel linear programming problem with fuzzy coefficients and variables in both objective functions and the constraints:(27)
max
⁡
x
~
-
1
~
⊗
x
~
⊕
4
~
⊗
y
~
max
⁡
y
~
1
~
⊗
y
~
s
.
t
.
-
2
~
⊗
x
~
⊕
1
~
⊗
y
~
≤
0
~
,
m
a
x
2
~
⊗
x
~
⊕
1
~
⊗
y
~
≤
12
~
,
m
a
x
-
3
~
⊗
x
~
⊕
2
~
⊗
y
~
≤
-
4
~
,
m
a
x
x
~
≥
0
,
y
~
≥
0
,where the membership functions of fuzzy coefficients of problem (27) can be expressed as (28)
μ
1
~
x
=
0
x
<
0
,
x
≥
2
x
0
≤
x
<
1
2
-
x
1
≤
x
<
2
,
μ
2
~
(
x
)
=
0
x
<
1
,
x
≥
3
x
-
1
1
≤
x
<
2
3
-
x
2
≤
x
<
3
,
μ
3
~
(
x
)
=
0
x
<
2
,
x
≥
4
x
-
2
2
≤
x
<
3
4
-
x
3
≤
x
<
4
,
μ
4
~
(
x
)
=
0
x
<
3
,
x
≥
5
x
-
3
3
≤
x
<
4
5
-
x
4
≤
x
<
5
,
μ
12
~
(
x
)
=
0
x
<
11
,
x
≥
13
x
-
11
11
≤
x
<
12
13
-
x
12
≤
x
<
13
,
μ
0
~
(
x
)
=
0
x
<
-
1
,
x
≥
1
x
+
1
-
1
≤
x
<
0
1
-
x
0
≤
x
<
1
.Now we deal with problem (29) by using the proposed approach in the previous section.Step 5.
Nineα-level sets are selected for computation, that is, α
=
0.1,0.2,0.3,0.4,0.5, 0.6,0.7,0.8, and 0.9, respectively.Step 6.
For anyα
∈
[
0,1
], problem (27) can be formulated as the following interval bilevel linear programming problem by using α-level sets of fuzzy numbers:(29)
max
⁡
-
[
α
,
2
-
α
]
⊗
x
α
±
⊕
[
3
+
α
,
5
-
α
]
⊗
y
α
±
max
⁡
[
α
,
2
-
α
]
⊗
y
α
±
s
.
t
.
-
[
1
+
α
,
3
-
α
]
⊗
x
α
±
⊕
[
α
,
2
-
α
]
⊗
y
α
±
max
⁡
≤
[
α
-
1,1
-
α
]
,
max
⁡
[
1
+
α
,
3
-
α
]
⊗
x
α
±
⊕
[
α
,
2
-
α
]
⊗
y
α
±
max
⁡
≤
[
11
+
α
,
13
-
α
]
,
max
⁡
-
[
2
+
α
,
4
-
α
]
⊗
x
α
±
⊕
[
1
+
α
,
3
-
α
]
⊗
y
α
±
max
⁡
≤
-
[
3
+
α
,
5
-
α
]
,
max
⁡
x
α
±
≥
0
,
y
α
±
≥
0
.Step 7.
Whenα
=
0.9, problem (29) can be transformed into two deterministic subproblems that correspond to the lower and upper bounds of the upper level objective function according to models (24) and (25), respectively. The first subproblem can be presented as follows:(30)
max
⁡
-
1.1
x
0.9
+
+
3.9
y
0.9
-
max
⁡
0.9
y
0.9
-
s
.
t
.
1.9
x
0.9
+
+
1.1
y
0.9
-
≤
11.9
,
max
⁡
-
1.9
x
0.9
+
+
1.1
y
0.9
-
≤
-
0.1
,
max
⁡
-
2.9
x
0.9
+
+
2.1
y
0.9
-
≤
-
4.1
,
max
⁡
x
0.9
+
≥
0
,
y
0.9
-
≥
0
.Based on the Kth-best algorithm, the solutions are x
0.9
*
+
=
4.1086, y
0.9
*
-
=
3.7214, F
0.9
*
-
=
9.9940, and f
0.9
*
-
=
3.3493. Thus, the second subproblem can be expressed as(31)
max
⁡
F
0.9
*
+
=
-
0.9
x
0.9
-
+
4.1
y
0.9
+
max
⁡
f
0.9
*
+
=
1.1
y
0.9
-
s
.
t
.
-
2.1
x
0.9
-
+
0.9
y
0.9
+
≤
0.1
,
2.1
x
0.9
-
+
0.9
y
0.9
+
≤
12.1
,
0.9
y
0.9
+
≤
4.2937
,
-
3.1
x
0.9
-
+
1.9
y
0.9
+
≤
-
3.9
,
-
y
0.9
+
≤
-
3.7214
,
x
0.9
-
≥
0
,
y
0.9
+
≥
0
.The solutions of problem (31) are x
0.9
*
-
=
3.9086, y
0.9
*
+
=
4.3245, F
0.9
*
+
=
14.2127, and f
0.9
*
+
=
4.5769. Consequently, when α
=
0.9, the lower and upper bounds of the upper level objective function are 9.9940 and 14.2127; and the lower and upper bounds of the lower level objective function are 3.3493 and 4.5769.Afterwards, the two subproblems under otherα-level sets (i.e., α
=
0.1,0.2,0.3,0.4,0.5, 0.6,0.7,0.8
) would be formulated in sequence and generate corresponding solutions, as presented in Table 1.Table 1
Results of the upper and lower bounds of objective values under different levels.
α
F
α
*
-
F
α
*
+
f
α
*
-
f
α
*
+
0.1
−3.2448
56.1503
0.2496
21.9296
0.2
−1.5827
45.4526
0.5158
17.3360
0.3
0.0206
37.6029
0.8038
14.0121
0.4
1.5947
31.5733
1.1187
11.5024
0.5
3.1666
26.7721
1.4667
9.5480
0.6
4.7635
22.8382
1.8545
7.9810
0.7
6.4130
19.5326
2.2905
6.7047
0.8
8.1450
16.6956
2.7846
5.6466
0.9
9.9940
14.2127
3.3493
4.5769Step 8.
According to (26), the optimal value of the upper level objective function of this example can be approximated by the linear piecewise trapezoidal fuzzy number: (32)
μ
F
~
*
(
t
)
=
0
t
<
-
3.2448
,
0.0602
t
+
0.2952
-
3.2448
≤
t
<
-
1.5827
,
0.0624
t
+
0.2987
-
1.5827
≤
t
<
0.0206
,
0.0635
t
+
0.2987
0.0206
≤
t
<
1.5947
,
0.0636
t
+
0.2985
1.5947
≤
t
<
3.1666
,
0.0626
t
+
0.3017
3.1666
≤
t
<
4.7635
,
0.0606
t
+
0.3112
4.7635
≤
t
<
6.4130
,
0.0577
t
+
0.3297
6.4130
≤
t
<
8.1450
,
0.0541
t
+
0.3595
8.1450
≤
t
<
9.9940
,
0.9
9.9940
≤
t
<
14.2127
,
-
0.0403
t
+
1.4724
14.2127
≤
t
<
16.6956
,
-
0.0352
t
+
1.3885
16.6956
≤
t
<
19.5326
,
-
0.0303
t
+
1.2909
19.5326
≤
t
<
22.8382
,
-
0.0254
t
+
1.1805
22.8382
≤
t
<
26.7721
,
-
0.0208
t
+
1.0576
26.7721
≤
t
<
31.5733
,
-
0.0166
t
+
0.9236
31.5733
≤
t
<
37.6029
,
-
0.0127
t
+
0.7790
37.6029
≤
t
<
45.4526
,
-
0.0093
t
+
0.6249
45.4526
≤
t
<
56.1503
,
0
t
≥
56.1503
.Based on statistical regression, the membership function for decision variable can be generated. Figures 1 and 2 present the membership functions of x
~ and y
~.Figure 1
The membership function ofx
~.Figure 2
The membership function ofy
~.


### 4.2. Analysis

In this section, we discuss variation in the range of the objective function values with the change ofα. It can be seen from Table 1 that different α-level sets would correspond to different upper and lower bounds of objective functions. With the increase of α, there is an increasing trend for the lower bounds of the upper and lower level objective functions while there is a decreasing trend for the upper bounds of the upper and lower level objective functions of the objective function. In addition, these results indicate that a smaller α-level set corresponds to a wider range of the objective function; conversely, the range of the objective function is narrower under a larger α-level set.From the point of view of the transformed models, the final obtained two submodels are bilevel linear programming problems which are the simplest models in bilevel programming. Therefore, the proposed method also has relatively low computational requirement due to the simplicity of its deterministic submodels.


## 4.1. Numerical Example

In this section, a numerical example is given to illustrate the proposed approach. Consider the following bilevel linear programming problem with fuzzy coefficients and variables in both objective functions and the constraints:(27)
max
⁡
x
~
-
1
~
⊗
x
~
⊕
4
~
⊗
y
~
max
⁡
y
~
1
~
⊗
y
~
s
.
t
.
-
2
~
⊗
x
~
⊕
1
~
⊗
y
~
≤
0
~
,
m
a
x
2
~
⊗
x
~
⊕
1
~
⊗
y
~
≤
12
~
,
m
a
x
-
3
~
⊗
x
~
⊕
2
~
⊗
y
~
≤
-
4
~
,
m
a
x
x
~
≥
0
,
y
~
≥
0
,where the membership functions of fuzzy coefficients of problem (27) can be expressed as (28)
μ
1
~
x
=
0
x
<
0
,
x
≥
2
x
0
≤
x
<
1
2
-
x
1
≤
x
<
2
,
μ
2
~
(
x
)
=
0
x
<
1
,
x
≥
3
x
-
1
1
≤
x
<
2
3
-
x
2
≤
x
<
3
,
μ
3
~
(
x
)
=
0
x
<
2
,
x
≥
4
x
-
2
2
≤
x
<
3
4
-
x
3
≤
x
<
4
,
μ
4
~
(
x
)
=
0
x
<
3
,
x
≥
5
x
-
3
3
≤
x
<
4
5
-
x
4
≤
x
<
5
,
μ
12
~
(
x
)
=
0
x
<
11
,
x
≥
13
x
-
11
11
≤
x
<
12
13
-
x
12
≤
x
<
13
,
μ
0
~
(
x
)
=
0
x
<
-
1
,
x
≥
1
x
+
1
-
1
≤
x
<
0
1
-
x
0
≤
x
<
1
.Now we deal with problem (29) by using the proposed approach in the previous section.Step 5.
Nineα-level sets are selected for computation, that is, α
=
0.1,0.2,0.3,0.4,0.5, 0.6,0.7,0.8, and 0.9, respectively.Step 6.
For anyα
∈
[
0,1
], problem (27) can be formulated as the following interval bilevel linear programming problem by using α-level sets of fuzzy numbers:(29)
max
⁡
-
[
α
,
2
-
α
]
⊗
x
α
±
⊕
[
3
+
α
,
5
-
α
]
⊗
y
α
±
max
⁡
[
α
,
2
-
α
]
⊗
y
α
±
s
.
t
.
-
[
1
+
α
,
3
-
α
]
⊗
x
α
±
⊕
[
α
,
2
-
α
]
⊗
y
α
±
max
⁡
≤
[
α
-
1,1
-
α
]
,
max
⁡
[
1
+
α
,
3
-
α
]
⊗
x
α
±
⊕
[
α
,
2
-
α
]
⊗
y
α
±
max
⁡
≤
[
11
+
α
,
13
-
α
]
,
max
⁡
-
[
2
+
α
,
4
-
α
]
⊗
x
α
±
⊕
[
1
+
α
,
3
-
α
]
⊗
y
α
±
max
⁡
≤
-
[
3
+
α
,
5
-
α
]
,
max
⁡
x
α
±
≥
0
,
y
α
±
≥
0
.Step 7.
Whenα
=
0.9, problem (29) can be transformed into two deterministic subproblems that correspond to the lower and upper bounds of the upper level objective function according to models (24) and (25), respectively. The first subproblem can be presented as follows:(30)
max
⁡
-
1.1
x
0.9
+
+
3.9
y
0.9
-
max
⁡
0.9
y
0.9
-
s
.
t
.
1.9
x
0.9
+
+
1.1
y
0.9
-
≤
11.9
,
max
⁡
-
1.9
x
0.9
+
+
1.1
y
0.9
-
≤
-
0.1
,
max
⁡
-
2.9
x
0.9
+
+
2.1
y
0.9
-
≤
-
4.1
,
max
⁡
x
0.9
+
≥
0
,
y
0.9
-
≥
0
.Based on the Kth-best algorithm, the solutions are x
0.9
*
+
=
4.1086, y
0.9
*
-
=
3.7214, F
0.9
*
-
=
9.9940, and f
0.9
*
-
=
3.3493. Thus, the second subproblem can be expressed as(31)
max
⁡
F
0.9
*
+
=
-
0.9
x
0.9
-
+
4.1
y
0.9
+
max
⁡
f
0.9
*
+
=
1.1
y
0.9
-
s
.
t
.
-
2.1
x
0.9
-
+
0.9
y
0.9
+
≤
0.1
,
2.1
x
0.9
-
+
0.9
y
0.9
+
≤
12.1
,
0.9
y
0.9
+
≤
4.2937
,
-
3.1
x
0.9
-
+
1.9
y
0.9
+
≤
-
3.9
,
-
y
0.9
+
≤
-
3.7214
,
x
0.9
-
≥
0
,
y
0.9
+
≥
0
.The solutions of problem (31) are x
0.9
*
-
=
3.9086, y
0.9
*
+
=
4.3245, F
0.9
*
+
=
14.2127, and f
0.9
*
+
=
4.5769. Consequently, when α
=
0.9, the lower and upper bounds of the upper level objective function are 9.9940 and 14.2127; and the lower and upper bounds of the lower level objective function are 3.3493 and 4.5769.Afterwards, the two subproblems under otherα-level sets (i.e., α
=
0.1,0.2,0.3,0.4,0.5, 0.6,0.7,0.8
) would be formulated in sequence and generate corresponding solutions, as presented in Table 1.Table 1
Results of the upper and lower bounds of objective values under different levels.
α
F
α
*
-
F
α
*
+
f
α
*
-
f
α
*
+
0.1
−3.2448
56.1503
0.2496
21.9296
0.2
−1.5827
45.4526
0.5158
17.3360
0.3
0.0206
37.6029
0.8038
14.0121
0.4
1.5947
31.5733
1.1187
11.5024
0.5
3.1666
26.7721
1.4667
9.5480
0.6
4.7635
22.8382
1.8545
7.9810
0.7
6.4130
19.5326
2.2905
6.7047
0.8
8.1450
16.6956
2.7846
5.6466
0.9
9.9940
14.2127
3.3493
4.5769Step 8.
According to (26), the optimal value of the upper level objective function of this example can be approximated by the linear piecewise trapezoidal fuzzy number: (32)
μ
F
~
*
(
t
)
=
0
t
<
-
3.2448
,
0.0602
t
+
0.2952
-
3.2448
≤
t
<
-
1.5827
,
0.0624
t
+
0.2987
-
1.5827
≤
t
<
0.0206
,
0.0635
t
+
0.2987
0.0206
≤
t
<
1.5947
,
0.0636
t
+
0.2985
1.5947
≤
t
<
3.1666
,
0.0626
t
+
0.3017
3.1666
≤
t
<
4.7635
,
0.0606
t
+
0.3112
4.7635
≤
t
<
6.4130
,
0.0577
t
+
0.3297
6.4130
≤
t
<
8.1450
,
0.0541
t
+
0.3595
8.1450
≤
t
<
9.9940
,
0.9
9.9940
≤
t
<
14.2127
,
-
0.0403
t
+
1.4724
14.2127
≤
t
<
16.6956
,
-
0.0352
t
+
1.3885
16.6956
≤
t
<
19.5326
,
-
0.0303
t
+
1.2909
19.5326
≤
t
<
22.8382
,
-
0.0254
t
+
1.1805
22.8382
≤
t
<
26.7721
,
-
0.0208
t
+
1.0576
26.7721
≤
t
<
31.5733
,
-
0.0166
t
+
0.9236
31.5733
≤
t
<
37.6029
,
-
0.0127
t
+
0.7790
37.6029
≤
t
<
45.4526
,
-
0.0093
t
+
0.6249
45.4526
≤
t
<
56.1503
,
0
t
≥
56.1503
.Based on statistical regression, the membership function for decision variable can be generated. Figures 1 and 2 present the membership functions of x
~ and y
~.Figure 1
The membership function ofx
~.Figure 2
The membership function ofy
~.


## 4.2. Analysis

In this section, we discuss variation in the range of the objective function values with the change ofα. It can be seen from Table 1 that different α-level sets would correspond to different upper and lower bounds of objective functions. With the increase of α, there is an increasing trend for the lower bounds of the upper and lower level objective functions while there is a decreasing trend for the upper bounds of the upper and lower level objective functions of the objective function. In addition, these results indicate that a smaller α-level set corresponds to a wider range of the objective function; conversely, the range of the objective function is narrower under a larger α-level set.From the point of view of the transformed models, the final obtained two submodels are bilevel linear programming problems which are the simplest models in bilevel programming. Therefore, the proposed method also has relatively low computational requirement due to the simplicity of its deterministic submodels.


## 5. Conclusion

In this paper, we deal with a class of bilevel linear programming problems in which all the coefficients and decision variables are fuzzy numbers. To solve these problems, we first discretize membership grade of fuzzy coefficients and fuzzy decision variables of the problem into a finite number ofα-level sets. For each α-level set, the original problem can be converted into an interval bilevel linear programming problem by using α-level sets of fuzzy numbers. Then we construct a pair of bilevel mathematical programming models which correspond to the lower and upper bounds of the upper level objective function of the obtained interval bilevel programming problem. Through the Kth-best algorithm, the two models can be solved sequentially. Based on a series of α-level sets, a linear piecewise trapezoidal fuzzy number is introduced to approximate the optimal value of the upper level objective function of the fully fuzzy bilevel linear programming problem. In the future, we will apply the proposed models and approach to solve some real world problems.



---

*Source: 280380-2015-03-16.xml*