2016 12th International Conference on Computational Intelligence and Security

A solution approach to bilevel linear programming

with fuzzy coefficients
Aihong Ren Xingsi Xue
Department of Mathematics School of Information Science and Engineering
Baoji University of Arts and Sciences Fujian Provincial Key Laboratory of Big Data Mining and Applications
Baoji, China Fujian University of Technology
raih2003@hotmail.com Fuzhou, China
xxs@fjut.edu.cn

Abstract—In this paper, we study the fuzzy bilevel program- bilevel programming problem where all coefficients in the
ming problem in which the coefficients in the objective functions objective functions as well as in the constraints are assumed
and the constraints are assumed to be fuzzy numbers. In to be fuzzy sets with known membership functions has been
comparison with deterministic bilevel programming, this kind of
problem is usually much more difficult to solve due to fuzziness considered in the literature. Zhang and Lu [12] defined the
involved in the problem. To handle such a problem, we first concept of optimal solution and proposed a fuzzy number
transform it into an interval bilevel programming in terms of based Kuhn-Tucher approach to solve the fuzzy bilevel pro-
α−level sets of fuzzy number. For the transformed interval gramming problem. Subsequently, the fuzzy Kuhn-Tucker ap-
bilevel problem, a new possibility degree of interval numbers is proach, the fuzzy Kth-best approach and the fuzzy branch-and-
applied to convert the interval constraints into equivalent forms
and the order relation of intervals is used to transform interval bound approach based on fuzzy set techniques were developed
objective functions into crisp ones. Based on these, the equivalent to deal with this kind of problem [13]. Ruziyeva and Dempe
deterministic bilevel programming can be obtained. Finally, a [14] suggested the Yager ranking indices approach to cope
numerical example is given to demonstrate the feasibility of the with a fuzzy bilevel programming problem. Recently, Hamidi
proposed approach. and Mishmast [15] used interval bilevel linear programming
Index Terms—Bilevel programming; Fuzzy bilevel program-
ming; Fuzzy sets; Interval number
to solve the fuzzy bilevel linear programming. In addition, a
membership function approach was presented to handle the
fuzzy bilevel linear optimization problem [16].
I. I NTRODUCTION
The aim of this paper is to develop a new method to solve
Bilevel programming provides an appropriate model to the fuzzy bilevel programming problem. To realize this, the
handle hierarchical decision processes consisting of two de- fuzzy bilevel programming is first reduced into an interval
cision makers. The decision makers at the upper and lower bilevel programming based on α−level sets of fuzzy number.
levels have their own objective functions and constraints. We make use of a new possibility degree of interval numbers
Each decision maker seeks to optimize their own objective to transform interval constraints into crisp constraints, and
function independently, but influences the decisions of the employ the order relation of interval numbers to convert inter-
other decision maker. To be more specific, the upper level val objective functions into crisp ones. Then the transformed
decision maker first selects a strategy, and then the lower level interval bilevel problem can be changed into a deterministic
decision maker reacts based on the selection of the upper level bilevel one solved by the Kth-best algorithm. Finally, we
decision maker. This kind of problem has been applied to a provide a numerical example to show the feasibility of the
rich variety of fields such as supply chain management [1], proposed approach.
[2], electricity markets [3], transport network design [4], [5]
This paper is organized as follows. Section 2 gives a
and principal-agent problems [6], [7]. However, one of the
formulation of the fuzzy bilevel linear programming problem.
main characteristics of bilevel programming is non-convex,
In Section 3, the solution approach is proposed to handle this
furthermore, such a problem is a NP-hard problem [8]. Thus
kind of problem. A numerical example is given to illustrate the
bilevel programming is generally difficult to cope with even
proposed models and approach in Section 4. Finally, Section
for the linear case of the problem. For decades, a number
5 concludes the paper with some remarks.
of researches have worked on theories, solution approaches
and applications of bilevel programming [9], [10]. It is worth
mentioning that the majority of these researches are based on
deterministic assumptions. II. P ROBLEM FORMULATION
However, in reality, the data involved in the bilevel program-
ming is often not known exactly and is only approximately
provided. In this case, the fuzzy set theory [11] is well suited to Consider the bilevel linear programming problem involving
tackle these uncertain data. Based on this approach, the fuzzy fuzzy coefficients in both objective functions and the con-

978-1-5090-4840-3/16 $31.00 © 2016 IEEE 78

DOI 10.1109/CIS.2016.25
straints as follows: transform interval inequality constraints and interval objectives
⎧ into crisp ones. Abass [17] used the possibility degree of inter-
⎪ min c̃11 x1 + c̃12 x2
⎪
⎪ x1 val numbers proposed by Zhang et al. [18] to reduce interval
⎪
⎪ where x2 solves
⎨ inequality constraints into crisp forms. However, this approach
min c̃21 x1 + c̃22 x2 (1) needs complicated formulas to compute the possibility degree.
⎪
⎪ x2
⎪
⎪ s.t. Ã1 x1 + Ã2 x2 ≤ b̃, Next, we adopt a new possibility degree of interval numbers
⎪
⎩
x1 ≥ 0, x2 ≥ 0, and the order relation of intervals to convert problem (2) into
a deterministic problem.
where x1 ∈ Rn1 and x2 ∈ Rn2 are the decision vectors
controlled by the upper and lower level decision makers, B. Conversion to a deterministic bilevel problem
respectively. c̃ij = (c̃ij1 , c̃ij2 , · · · , c̃ijnj ), i = 1, 2, j = In order to deal with problem (2), we first change the
1, 2, are nj -dimensional vectors whose elements c̃ijk , k = interval inequality constraints into the corresponding crisp
1, 2, · · · , nj , are fuzzy numbers. Ãj = (ãlj1 , ãlj2 , · · · , ãljnj ), equivalent forms. As we know, the possibility degree of
l = 1, 2, . . . , q, are q × nj −dimensional fuzzy matrices whose interval numbers can be used to represent certain degree of
elements ãljm , m = 1, 2, · · · , nj , are fuzzy numbers, and b̃ is one interval being larger or smaller than another. Taking into
an q−dimensional fuzzy vector. account ease of computation, a new possibility degree of
Differently from deterministic bilevel programming, prob- interval numbers in [19] is employed to deal with interval
lem (1) is ill-defined due to the existence of fuzziness. inequality constraints of problem (2).
In other words, the meaning of minimizing both objective For two intervals aI = [a− , a+ ] and bI = [b− , b+ ], the
functions and constraints is unclear. As a result, we can not possibility degree of interval numbers aI and bI can be
employ blindly solution concepts and solution approaches for calculated by the following equation [19]:
deterministic bilevel programming to deal with this type of min(b+ − a+ , b+ − b− )
problem. It needs to develop a potential method to tackle the P (aI ≤ bI ) = max{ , 0}.
b+ − b−
problem.
Comparing with the possibility degree of interval numbers
III. T HE OPTIMIZATION PROCEDURE proposed by Zhang et al. [18], the definition of the possibility
degree developed by [19] has the merits of simple formula
In this section, we apply α−level sets of fuzzy number
and ease of computation.
as well as a new possibility degree of interval numbers and
Based on the above definition of the possibility degree,
the order relation of intervals to transform equivalently the
the lth interval inequality constraint of problem (2) can be
fuzzy bilevel programming problem into a deterministic bilevel
transformed into the deterministic constraint as follows:
programming problem.

n1 
n2
P { [a− +
l1sα , al1sα ]x1s + [aL R
l2tα , al2tα ]x2t
A. Conversion to an interval bilevel programming problem s=1 t=1

It is well known that an α−level set of a fuzzy number ≤ [bL R

lα , blα ]} ≥ λl

n1 
n2
is an interval number. Then fuzzy coefficients of problem (1) ⇔ aR
l1sα x1s + aR R L
l2tα x2t ≤ (1 − λl )blα + λl blα .
can be replaced by the corresponding α−level sets. Therefore, s=1 t=1

problem (1) can be formulated as the following interval bilevel where λl ∈ [0, 1] is a predetermined possibility degree level
linear programming problem for some α ∈ (0, 1] as follows: for the lth constraint, l = 1, 2, · · · , q.
⎧ Next we treat both interval objective functions of problem
⎪ min [c− + − +
11α , c11α ]x1 + [c12α , c12α ]x2
⎪
⎪ x1 (2). One common approach to handle uncertain objective
⎪
⎪
⎨ where x2 solves functions in interval programming is to use the order relation
min [c− + − +
21α , c21α ]x1 + [c22α , c22α ]x2 (2) of intervals to rank interval numbers. Here we can minimize
⎪
⎪ x2
⎪
⎪ [A −
, A +
]x + [A −
, A +
]x ≤ [b− +
, b ],
their right limits and midpoint values simultaneously according
⎪
⎩ s.t. 1α 1α 1 2α 2α 2 α α
to the order relation proposed by Chanas and Kuchta [20].
x1 ≥ 0, x2 ≥ 0,
Hence the interval objective functions of the upper and lower
where [c− + − + − +
ijα , cijα ], i = 1, 2, j = 1, 2, [Ajα , Ajα ] and [bα , bα ]
levels can be changed to two objective functions as follows:
are the α−level sets of fuzzy coefficients c̃ij , Ãj and b̃, respec- c− +c+ c− +c+
min (c+ +
i1α x1 + ci2α x2 ,
i1α i1α
x1 + i2α i2α
x2 ),
tively. [c− +
ijα , cijα ] are nj -dimensional interval vectors whose
xi 2 2

elements [cijkα , c+
− i = 1, 2.
ijkα ], k = 1, 2, · · · , nj , are interval numbers.
[A−jα , A +
jα ] are q × nj −dimensional interval matrices whose Next, we use the linear combination method to aggregate
elements [a− , a +
ljmα ljmα ], l = 1, 2, . . . , q, m = 1, 2, . . . , nj , are
the two objectives of the upper and lower levels into a single
interval numbers, and [b− +
α , bα ] is an q−dimensional interval
objective. In this way, the above two objective functions can
vector. be rewritten as:
Through the above formulation, we can obtain an interval c− +c+
min γi (c+ +
i1α x1 + ci2α x2 ) + (1 − γi )(
i1α
2
i1α
x1 +
bilevel programming problem which is still not a well-defined xi
c− +c+
problem. For this kind of problem, a key question is how to i2α
2
i2α
x2 ), i = 1, 2.

79
 Equivalently, This example can be transformed as the following problem
through α−level sets of fuzzy number:
min 1
2 [((1 − γi )c− +
i1α + (1 + γi )ci1α )x1 + ⎧
xi min [α, 2 − α]x − [α + 3, 5 − α]y
((1 − γi )c− + ⎪
⎪
i2α + (1 + γi )ci2α )x2 ], i = 1, 2. ⎪ x≥0
⎪
⎪
⎪
⎪ where y solves
⎪
⎪
Based on the above treatments, problem (2) can be trans- ⎪
⎪ min [α, 2 − α]y
formed into the following problem: ⎨ y≥0
s.t. [α + 1, 3 − α]x − [α, 2 − α]y ≥ [α − 1, 1 − α],
⎧ ⎪
⎪
⎪
⎪ min 12 [((1 − γ1 )c− +
11α + (1 + γ1 )c11α )x1 + ⎪
⎪ −[α + 1, 3 − α]x − [α, 2 − α]y ≥
⎪
⎪ x1 ⎪
⎪ −[α + 11, 13 − α],
⎪ ((1 − γ1 )c− + ⎪
⎪
⎪
⎪ 12α + (1 + γ1 )c12α )x2 ] ⎪
⎪
⎪
⎪ ⎪
⎩ [α + 2, 4 − α]x − [α + 1, 3 − α]y ≥
⎪
⎪ where x2 solves
⎪
⎪ [α + 3, 5 − α].
⎨ min 12 [((1 − γ2 )c− +
21α + (1 + γ2 )c21α )x1 + (5)
x2
((1 − γ2 )c− + (3)
⎪
⎪ 22α + (1 + γ2 )c22α )x2 ] In terms of model (3), the above problem can be converted
⎪
⎪ 1 +
n 2 +
n
⎪
⎪ al1sα x1s + al2tα x2t ≤
into the following deterministic bilevel problem:
⎪
⎪
s.t.
⎧
⎪
⎪ s=1 t=1 min (γ1 − γ1 α + 1)x + (γ1 − γ1 α − 4)y
⎪
⎪ + −
(1 − λ)blα + λblα , l = 1, 2, · · · , q, ⎪
⎪
⎪
⎩ ⎪ x≥0
⎪
x1 ≥ 0, x2 ≥ 0, ⎪
⎪ where y solves
⎪
⎪
⎪
⎪ min (γ2 − γ2 α + 1)y
⎪
⎪
where γ1 , γ2 ∈ (0, 1) represent the weighting factors. ⎪ y≥0
⎨ s.t. [(1 − λ1 )(3 − α) + λ1 (α + 1)]x−
Obviously, problem (3) is a classical bilevel linear program- (6)
⎪
⎪ [(1 − λ1 )α + λ1 (2 − α)]y ≥ 1 − α,
ming problem. Here the Kth-best algorithm proposed by Bialas ⎪
⎪ [−(1 − λ2 )(α + 1) + λ2 (α − 3)]x−
⎪
⎪
et al. [21] can be employed to solve this kind of problem. ⎪
⎪ [(1 − λ2 )α + λ2 (2 − α)]y ≥ −11 − α,
⎪
⎪
⎪
⎪ [(1 − λ3 )(4 − α) + λ3 (α + 2)]x−
IV. N UMERICAL E XAMPLE ⎪
⎩
[(1 − λ3 )(α + 1) + λ3 (3 − α)]y ≥ 5 − α.
To demonstrate the feasibility of the proposed models
We set the values of parameters of model (6) as α = 0.6,
and method, let’s consider the following fuzzy bilevel linear
β1 = β2 = 0.7, λ1 = λ2 = λ3 = 0.5. We solve problem
programming problem in [15]:
⎧ (6) by using the Kth-best algorithm and obtain the optimal
⎪
⎪ min 1̃x − 4̃y solution (x∗ , y ∗ ) = (3.9143, 3.6714).
⎪
⎪ x≥0
⎪
⎪ where y solves
⎪
⎪ V. C ONCLUSION
⎨
min 1̃y In this paper, we deal with a class of bilevel linear program-
y≥0 (4)
⎪
⎪ s.t. 2̃x − 1̃y ≥ 0̃, ming problems involving fuzzy coefficients in both objective
⎪
⎪
⎪
⎪ ˜ functions and the constraints. To handle these problems, we
⎪
⎪ −2̃x − 1̃y ≥ −12,
⎩ first employ α−level sets of fuzzy number to transform the
3̃x − 2̃y ≥ 4̃.
fuzzy bilevel programming into an interval bilevel program-
˜ 0̃ are characterized by
where fuzzy coefficients 1̃, 2̃, 3̃, 4̃, 12, ming. Then a new possibility degree of interval numbers
the following⎧ membership functions respectively: is used to give the equivalent transformations of interval
⎨ 0 x < 0, x ≥ 2 inequality constraints, and the order relation of interval num-
μ1̃ (x) = x 0≤x<1 , bers is applied to convert interval objective functions into
⎩
⎧ 2−x 1≤x<2 deterministic ones. Then we can obtain a deterministic bilevel
⎨ 0 x < 1, x ≥ 3 one solved by the Kth-best algorithm. Finally, a numerical
μ2̃ (x) = x−1 1≤x<2 , example is provided to demonstrate the feasibility of the
⎩
⎧ 3 − x 2 ≤ x < 3 proposed approach for solving such problems.
⎨ 0 x < 2, x ≥ 4
ACKNOWLEDGMENT
μ3̃ (x) = x−2 2≤x<3 ,
⎩ This work was supported by the National Natural Science
⎧ 4 − x 3 ≤ x < 4
⎨ 0 x < 3, x ≥ 5 Foundation of China (No.61602010) and Science Foundation
μ4̃ (x) = x−3 3≤x<4 , of Baoji University of Arts and Sciences (No.ZK16049).
⎩
⎧ 5 − x 4 ≤ x < 5 R EFERENCES
⎨ 0 x < 11, x ≥ 13
[1] T. Kis and A. Kovács, “Exact solution approaches for bilevel lot-sizing,”
μ12
˜ (x) = x − 11 11 ≤ x < 12 , European Journal of Operational Research, vol. 226, no. 2, pp. 237-245,
⎩
⎧ 13 − x 12 ≤ x < 13 2013.
[2] D. P. Wang, G. Du, R. J. Jiao, R. Wu, J. P. Yu and D. Yang, “A Stack-
⎨ 0 x < −1, x ≥ 1
elberg game theoretic model for optimizing product family architecting
μ0̃ (x) = x + 1 −1 ≤ x < 0 . with supply chain consideration,” International Journal of Production
⎩
1−x 0≤x<1 Economics, vol. 172, pp. 1-18, 2016.

80
[3] G. Zhang, G. Zhang, Y. Gao and J. Lu, “Competitive strategic bidding
optimization in electricity markets using bilevel programming and swarm
technique,” IEEE Transactions on Industrial Electronics, vol. 58, no. 6,
pp. 2138-2146, 2011.
[4] F. Gzara, “A cutting plane approach for bilevel hazardous material
transport network design,” Operations Research Letters, vol. 41, no. 1,
pp. 40-46, 2013.
[5] P. Fontaine and S. Minner, “Benders decomposition for discrete-
continuous linear bilevel problems with application to traffic network
design,” Transportation Research Part B Methodological, vol. 70, pp.
163-172, 2014.
[6] M. Cecchini, J. Ecker, M. Kupferschmid and R. Leitch, “Solving non-
linear principal-agent problems using bilevel programming,” European
Journal of Operational Research, vol. 230, no. 2, pp. 364-373, 2013.
[7] M. W. Xu and J. J. Ye, “A smoothing augmented Lagrangian method
for solving simple bilevel programs,” Computational Optimization &
Applications, vol. 59, no. 1, pp. 353-377, 2014.
[8] J. F. Bard, “Some properties of the bilevel linear programming,” Journal
of Optimization Theory and Applications, vol. 68, no. 2, pp. 146-164,
1991.
[9] S. Dempe, Foundations of Bilevel Programming, Kluwer Academic
Publishers, Dordrecht, Boston, London, 2002.
[10] B. Colson, P. Marcotte and G. Savard, “An Overview of Bilevel
Optimization,” Annals of Operations Research, vol. 153, no. 1, pp. 235-
256, 2007.
[11] L. A. Zadeh, “Fuzzy Sets,” Information and Control, vol. 8, no. 3, pp.
338-353, 1965.
[12] G. Q. Zhang and J. Lu, “The definition of optimal solution and an
extended Kuhn-Tucker approach for fuzzy linear bilevel programming,”
IEEE Intelligent Informatics Bulletin, vol. 6, no. 2, pp. 1-7, 2005.
[13] G. Q. Zhang, J. Lu and T. Dillon, “Fuzzy linear bilevel optimization:
solution concepts, approaches and applications,” Studies in Fuzziness and
Soft Computing, vol. 215, pp. 351-379, 2007.
[14] A. Ruziyeva and S. Dempe, “Yager ranking index in fuzzy bilevel
optimization,” Artificial Intelligence Research, vol. 2, pp. 55-68, 2013.
[15] F. Hamidi and N. Mishmast, “Bilevel linear programming with fuzzy
parameters,” Iranian Journal of Fuzzy Systems, vol. 10, no. 4, pp. 83-99,
2013.
[16] A. Ruziyeva, Fuzzy Bilevel optimization [Ph.D. thesis], Freiberg: Tech-
nical University, 2013.
[17] S. A. Abass, “An interval number programming approach for bilevel
linear programming problem,” International Journal of Management
Science and Engineering Management, vol. 5, no. 6, pp. 461-464, 2010.
[18] Q. Zhang, Z. Fan and D. Pan, “A ranking approach for interval numbers
in uncertain multiple decision making problem,” Systems Enginseering -
Theory & Practice, vol. 5, pp. 129-133, 1999.
[19] C. Y. Qin and W. Li, “Possibility degree and improvement solution of
the interval linear programming,” Journal of Hangzhou Dianzi University,
vol. 31, no. 3, pp. 74-77, 2011.
[20] S. Chanas and D. Kuchta, “Multiobjective programming in optimization
of interval objective functions-a generalized approach,” European Journal
of Operational Research, vol. 94, no. 3, pp. 594-598, 1996.
[21] W. F. Bialas and M. H. Karwan, “Two-level linear programming,”
Management Science, vol. 30, no. 8, pp. 1004-1020, 1984.

81