American Journal of Oper ations Research, 2011, 1, 214-219
doi:10.4236/ajor.2011.14024 Published Online December 2011 (http://www.SciRP.org/journal/ajor)
Solving Bilevel Linear Multiobjective
Programming Problems
Calice Olivier Pieume1, Patrice Marcotte2, Laure Pauline Fotso3, Patrick Siarry4
1Department of Mat hem at i cs, Faculty of Science, University of Yaounde I, Yaounde, Cameroon
2Department of Comp ut er Sci ence an d O per at i on s Research, University of Montreal, Montreal, Canada
3Departme n t of Compute r Sc iences, Faculty of Science, University of Yaounde I, Yaounde, Cameroon
4LISSI, Faculty of Sciences and Technology, University of Paris XII Val-de-Marne, Paris, France
Received July 27, 201 1; revised August 28, 2011; accepted September 10, 2011
Abstract
This study addresses bilevel linear multi-objective problem issues i.e. the special case of bilevel linear pro-
gramming problems where each decision maker has several objective functions conflicting with each other.
We introduce an artificial multi-objective linear programming problem of which resolution can permit to
generate the whole feasible set of the upper level decisions. Based on this result and depending if the leader
can evaluate or not his preferences for his different objective functions, two approaches for obtaining Pareto-
optimal solutions are presented.
Keywords: Multiobjective Programming, Bilevel Programming, Feasible Solution, Pareto-Optimal
Solutions
1. Introduction
Bilevel programming problems occur in diverse applica-
tions, such as transportation, economics, ecology, engi-
neering and others. They have been extensively studied
in the literature [1-3]. However, when facing a real-
world bilevel decision problem, the leader and the fol-
lower may have multiple conflict objectives that should
be optimized simultan eously for achieving a solution [4].
There are only very few approaches in the literature
dealing with bilevel multiobjective problems: less than a
dozen of paper in the literature are related to this par-
ticular class of problems to our knowledge [5-8]. Three
reasons at least can explain the fact that the issue has not
yet received a broad attention in the literature: the diffi-
culty of searching and defining optimal solutions; the
lower level optimization problem has a number of trade-
off optimal solutions; and it is computationally more
complex than the conventional Multi-Objective Pro-
gramming Problem or a bilevel Programming Problem.
Consequently, it is extremely desirable to develop a sim-
ple and practical technique that can permit to find effi-
cient solutions for this class of bilevel programming
problem.
This study addresses linear multi-objective problem
issues. The optimistic formulation is considered. We
introduced an artificial multi-objective linear program-
ming problem of which the resolution can permit to gen-
erate the whole set of feasible points of the upper level
decisions. Based on this result and depending if the
leader can evaluate or not his preferences for his differ-
ent objective functions, two approaches for obtaining
Pareto-optimal solutions are presented.
The paper is organized as follows. In the next section,
we recall some notions about the solving of multiobjec-
tive programming problems (BLMPP). In Section 3, the
optimistic formulation of a bilevel linear multi-objective
programming problem is presented. Section 4 presents a
relation between the feasible set of the upper level deci-
sions and the Pareto-optimal set of a particular multi-
objective programming problem introduced. Section 5
presents two approaches for solving BLMPP, based on
the new relation established. Finally, the paper is con-
cluded in Section 6.
2. Efficient Points in Multiobjective
Programming
A multi-objective programming problem is formulated in

C. O. PIEUME ET AL. 215

general as follows:
 

12
"min",,, Q
xhxh xhxhx
,
s
txU
Q
(MOPP)
where is the objective function vector and
the set of constraints.
:n hR R
n
RU
Due to the fact that, for , there is no canonical
(total) order in , as there is on , one has to define
how objective function vector
Q2
Q
RR
  
12
,,,
Q
hxhxh x

must be compared for different alternatives
x
U

.
Closed pointed convex cones are generally used for the
derivation of partial orders in the decision space. Let
K
be an arbitrary cone such that
K
Q R, then the binary
relation with respect to the cone
K
(denoted
K

) is
defined by:
K
ab if and only if baK
Due to the fact that it could not be possible to find a
solution that optimizes simultaneously all the objective
functions, a weaker concept, the concept of N on-domi-
nated poi nt is used.
Definitio n 1 .
A point

0
y
hU is a non-dominated point with
respect to the cone
K
if and only if there does not exist
a point

y
hUy, 0, such that 0K. If yyy*
y
is a non-dominated point with respect to the cone K, then
*
x
U, such that is called Pareto-optimal
(or efficient) solution with respect to the cone

*
yh

x
*

K
.
The following definition of efficient points is the most
used in the literature [9-11].
Definitio n 2 .
A feasible point *
x
U is called Pareto-optimal if
there does not exist
x
U such that
  





** *
121 2
,,,, ,,
Q
hxhxhxhxhxhx

Q

and
 




 
** *
121 2
,,,, ,,
QQ
hxhxhxhxhxhx
If *
x
is Pareto-optimal, then is called non-
dominated point.

*
hx
Let us remark that Definition 2 is a particular case of
Definition 1, where the cone used is . Pareto-
optimal points are then solutions that cannot be improved
in one objective function without deteriorating their per-
formance in at least one of the other objective functions.
Through the paper, the set of efficient points of a multi-
objective optimization problem defined by a vector func-
tion value h on a feasible set U, with respect to a cone

\0
QQ
R
K
, will be denoted by


K
,,EhU and the corre-
sponding non-dominated set denoted by

,,
K
NhU

.
Unfortunately, for a majority of MOPP, it is not easy
to obtain an exact description of the efficient set, that
typically includes a very large or infinite number of
points. Solving multiobjective programming problems
consists in general to find a finite subset of the efficient
set and present them for evaluation to the decision maker
(DM). A set is a good representation of the efficient
set W


K
,,EhU

if the following three conditions are
fulfilled: is finite and contain a reasonable number
of points; non-dominated points corresponding to W
do not miss a large portion of
W

,,
K
NhU
 
hy
(coverage
criterion); and these points do not include points that are
very close to each other (uniformity criterion).
The coverage error is mathematically defined by:


,,
max min,
KyW
xEhU dhx




where


.,.d is a given distance defined in the decision
space. This measure can be seen as the error associated
to the worst representation of an element of


,,K UEh

in W. The uniformity of a representation
is mathematically defined by:
 
,;
min d,
yzWy zhy h



 
z
It measures the distance between a pair of closed ele-
ments of . A smaller number of points, a lower cov-
erage error and a more uniform level are desirable in
order to have a good representation of the efficient set.
Such subsets are called representative subsets of the effi-
cient set. Approaches that could generate a representative
subset of the efficient set when solving linear multicrite-
ria optimization problems, can be found in [9- 1 1] .
W
3. Optimistic Formulation of a BLMPP
A standard Bilevel Programming Problem (BPP) can be
modeled as follows:



min ,
0
min
subject to solve,
xX
yY
Fxy
Gx


,
,0
f
xy
y
yst
gx


 








(BPP)
where 1
n
x
XR ; 2
n
y
YR ; ,:
F
fXY R


,:X YR
are the outer (planner’s or leader’s) problem objective
function and the inner (behavioral or follower’s) problem
objective function, respectively; are
inequality constraints. Gg


x
resp y are decision variables
controlled by the leader (resp the follower).
If
F
and
f
are vector value fun ctions

C. O. PIEUME ET AL.
216

12 1122
: and :
nn mnn m
FR RRfR RR ,
then one speak about bilevel multiobjective program-
ming problems (BMPP). The standard formulation of a
(BMPP) can then be as follows (Equation (1)):
Our focus will be on the linear formulation of a BMPP,
given as follows:
 





1
1
2
2
12
11
12
232
min ,,,,,,,
min,,, ,
, solves
n
n
m
xR
m
yR


F
xyC xy CxyCxy
Ax b
f
xycycycy
st yst
Ax Ayb




















(BLMPP)
where are 21 ,1,,
i
Ci m1 nn

-dimensional constant
row vectors; 2i are 2-dimensional con-
stant row vectors; 1 is a p-dimensional constant col-
umn vector and is a q-dimensional constant column
vector; 1
,1cib
2
b
,,mn
A
is a constant matrix; 21 pn
A
is a 1 qn

constant matrix and 3
A
a q2 n

constant matrix.
Let us denote by , the set of rational responses
of the follower, for each decision

Rx

x
of the leader. It is
defined as the Pareto-optimal point of the following
problem:


2
212
322
min,,,,
.
nm
yR
f
xycycyc y
stA ybA x





with this notation, one has the following formulation of
BLMPP:
 


1
12
11
min ,,,,,,,
Subject to
m
xX
F
xyC xy CxyCxy
Ax b
yRx








Using also the following representation for the feasible
space of BLMPP:
 

12
11
, and
nn

x
yRRAxb yRx

 
One obtains then the following optimistic formulation
of BLMPP:
 



1
12
,
min ,,,,,,,
.
,
m
xy
F
xyC xy CxyCxy
st
xy



(BMPP’)
We present in the following section a theoretical result
that will be used after to derive two algorithms for solv-
ing BLMPP’. Through all the rest of the paper,
Z
represents the set defined as follows:



12
11 232
, and
nn
Z
xyRRAx bAx Ayb

 
It is assumed that
Z
is a non-empty and bounded set
over the convex polyhedron. We call S the solution set of
the problem BLMPP’.
4. A New Characterization of the Feasible
Set of a BLMPP
We introduce a multi-objective programming problem of
which efficient set is exactly equivalent to the feasible
set of BLMPP’. A similar result has already been devel-
oped in [5], but with a different multiobjective program-
ming problem. The result of the author is as follows.
Consider the following multi-objective programming
problem:



2
12
,
11
232
min,,, ,,
.
0, 0
m
xy
f
xycycycyx
st
Ax b
Ax Ay b
xy





(MPP2)
Let




2\0 0
mmn
KR


21
1 and be as defined
above. The following result holds: 
Lemma 1.


,,K EfZ 

1
The inconvenient of this result is that it is not easily
applicable. In fact, there does not exist approaches de-
veloped in the literature for finding efficient points with
respect to the particular cone



2\0 0
mmn
KR


21
1.
Methods are usually for cones that have the form


\0
nn
R, nR

. It is the reason why in [5], the author
approximates the efficient set of MPP2 by the weakly
efficient set.
 






 


1
2
12
12
min ,,,,,,,
0
min ,,,,,,,
, solves
,0
m
xX
m
yY
FxyFxy F xyFxy
Gx

f
xyf xyfxyfxy
st yst
gxy
















 (BMPP) (1)

217 C. O. PIEUME ET AL.
We introduce now a new relation that could be applied
directly.
Let us consider the following multi-objective linear
programm ing pr o blem:

,
11
232
0
min ,0
0
.
0, 0
xy t
c
x
Hxy Iy
e
st
Ax b
Ax Ayb
xy

 
 







(LMPP1)
where is a 22
matrix with rows i cs; is a
vector having each entry equal to 1 and
cmne
I
is an 11 nn

identity matrix. Recall that each i represents the row
vector that defined the ith-objective function of the fol-
lower. Let , then the following
result holds.
c


21
1
2
\0
mn 



21
mn
KR

1
Theorem 1.

2
,,K EHZ 
Proof:
 Let us show that

2
,,K EHZ
Let , from the definition
of , one has naturally


2
00
,,,
K
zxy EHZ 

2
,,K EHZ2030 2
A
xAyb
and 10 1
A
xb. So, in order to show that , it suf-
fices to show that 0
z

0
y
Rx. Let us suppose the con-
trary. Then there exist
y
such that: 1) 2032
A
xAyb
and 2)
y
dominate .
0
Relation 2) is equivalent to
y

2
1210200
,,,, ,,
m
cycyc ycycyc y

2
m

m with at least one such that

2
1, ,k0kk cycy

.
Let now consider the point

0,zxy
*, we have:
0 *0
0
0
0
0t
t
cc
xy
H
zI x
yex
e

 
 







y
and
0
00
00
0
0
0t
t
cc
x
H
zI x
yex
e



 






Due to relation 2), one has 0
cy cy and 0 cy cy

,
this permit to deduct that:
0 0
0
x
x
HH
y y




 
and 0
0
0
x
x
HH
y y




 
So

0,

x
y dominate

00
,

x
y

21
mn  
with respect to the
cone , which contradict the fact

21
1
2
\0
mn
KR


1


00
,
x
y is a Pareto-optimal point with respect to the
cone


21
21
1
21
\0
mn mn
KR






2
,,K EHZ

00
,zxy
.
 Let us show that
Suppose that there is such that 


,,K HZ
2. Then there most be a point zE


1
y111 ,zx such that
H
z dominates
H
z. This im-
plies that 1
H
zHz

and 1
H
zHz. Using the structure
of the matrix
H
, and the fact that and

00
,y

zx


1
y
1
1
0
0
ccy
x
11
,zx , one obtains:
10
0
10
0
10
0
00
0
tt
tt
c
xcy
I
xI x
yex
ee

 







yex

 






cy



and then
10
10
10
tt
cy
x
x
ex






ex






10
xx

This implies that: 0

 and

100
t
exx

,
which means that 10
x
x

and also 10 . It fol-
lows that
tt
ex ex
10
cy cy

and 10 cy . This implies that 1
dominates . Contradicting the fact that
cy
yy
0


00
y
Rx.
From this theorem, one can deduce that solving our
problem (BLMPP’) is equivalent to solve:
 


1
12
,,,,,
m


2
,
min ,,
.
,,,
xy
K
F
xyC xy
st
xy EHZ


C xyCxy
(BLMPP”)
The theorem led to the following corollary.
Corollary 1.



21
,,,,
KK
HZSEFE  where


1
\0
mKR
,
m
1
1m
KR


,,
and .

21
12
1
21
\0
mn mm 

We present now two approaches for solving BLMPP’
based on this last result.
5. Two Approaches for Solving a B L M P P
5.1. First Approach
Suppose that the upper decision maker is fully knowl-
edgeable about all his preferences. One could then ag-
gregate the leader objective functions using the weights
1
12

  

1
,1
min ,
. ,
i
m
mi
xy i
Cx
stx yE



that measure his preference concerning
different objective functions. Solving BLMPP’ will be
then equivalent to solve the following problem:


2
,, K
y
H Z

C. O. PIEUME ET AL.
218

11
232
,
0, 0
s
t
Ax b
A
xAyb
xy




(LMPP1)
The obtained problem consists in an optimization of a
linear function over a Pareto-optimal set. They are many
approaches, developed in the literature, that are devoted
to the optimization of a linear function over an efficient
set (see [12], or the survey presented by Y. Yamamoto in
[13] or C.O. Pieume and al in [14]). Any of these ap-
proaches can then be applied. Step 2: Compute a representative subset (called )
of the efficient set of LMPP1. S
 For instance, approaches developed in [9-11] can be
used.
Step 3: Compute the image set of by S




F
YFS.
Step 4: Find non-dominated points of (called )
with respect to Yeff
Y
F
.
Step 5: Find the Pareto-optimal points set
E
X
cor-
responding to .
5.2. Second Approach
The second approach could be to generate a representa-
tive subset of 2 using well known scheme
[9-11], as described in the first section. Then one com-
putes the image of the obtained subset by the leader ob-
jective functions and selects elements that led to
non-dominated po ints for the leader. The following algo-
rithm seems to be natural.

,,K EHZ
eff
 The Pareto-filter approach presented in [10] can be
used in Step 4 and Step 5.
Y
Step 1: Construct the following multiobjective linear
programm ing pr o blem: Step 6:
E
X
is a representative subset of the efficient
set of BMLPP’, STOP.

,
0
min ,0
0
xy t
c
x
Hxy Iy
e



 




5.3. Illustrative Example
Let consider the following problem [15].


12
12
1212
,
12
12
1212
,
112
21
12 2
12
max2 ,3
3
,0
max3 ,2
subject to:6 ,
where solves 3
8
,0
xx
yy
xxxx
xx
xx
yyyy
xyy st
yxy
xxy
yy









 









The solution obtained by the authors [15] is the
unique point

with values of leader objective functions and follower
objective functions respectively equal to

1212
,, ,1.5,1.5,4.1154,3.3846xxyy 



*4.5,6F

92,11.6154 and .
*14.26f
multiobjective linear programming problem introduced.
Two approaches have then been proposed in order to
generate efficient points. The first approach aggregates
the leader objective function and suggests to use a tech-
nique of optimization of linear function over an efficient
The following Table 1 presents non dominated points
provided by the second approach: Table 1. Non dominated points.
Consequently, Pareto-optimal points obtained are the
points presented in the Table 2. 6.3.54.256.6.5.14.9001736 6. 5.254.125
3. 8.6.5 3.3.4.84.9826389 3. 4.5 6.75
Figure 1 illustrates non-dominated points provided by
the last approach (red points).
Table 2. Pareto-optimal points.
6. Conclusions 0.2.51.750.0. 0.9 1.0130208 0. 0.751.875
3.0.51.253.3. 2.1 1.9435764 3. 2.251.125
6.3.54.251.2.6254.2251.9696181 3.5625 5.253
0.5.3.55.3.3752.6755.0434028 2.4375 1.50
We have established in this paper equivalence between
the feasible set of a bilevel multiobjective linear pro-
gramming and the set of efficient points of an artificial

219 C. O. PIEUME ET AL.
Figure 1. Representation of non dominated points.
set, in order to find an optimal solution. The second ap-
proach uses a Pareto-filter scheme to find an approxi-
mated discrete representation of the efficient set. The
second approach has the advantage to keep the multi-
criteria concept of the upper DM, while the first one uses
an aggregation process to eliminate the multi-criteria
concept for the leader. We hope that this research can
benefit the development of decision support systems for
tackling bilevel multi-objective linear optimization prob-
lems in the real world.
7. References
[1] B. Colson, P. Marcotte and G. Savard, “An Overview of
Bilevel Optimization,” Annals of Operational Research,
Vol. 153, No. 1, 2007, pp. 235-256.
doi:10.1007/s10479-007-0176-2
[2] J. Fulop, “On the Equivalence between a Linear Bilevel
Programming Problem and Linear Optimization over the
Efficient Set,” Technical Report WP93-1, Laboratory of
Operations Research and Decision Systems, Computer
and Automation Institute, Hungarian Academy of Sci-
ences, 1993.
[3] C. O. Pieume, L. P. Fotso and P. Siarry, “A Method for
Solving Bilevel Linear Programming Problem,” Journal
of Information and Optimization Science, Vol. 29, No. 2,
2008, pp. 335-358.
[4] Y. Yin, “Multiobjective Bilevel Optimization for Trans-
portation Planning and Management Problems,” Journal
of Advanced Transportation, Vol. 36, No. 1, 2000, pp.
93-105. doi:10.1002/atr.5670360106
[5] G. Eichfelder, “Multiobjective Bilevel Optimization,”
Mathematical Programming, Vol. 123, No. 2, 2008, pp.
419-449. doi:10.1007/s10107-008-0259-0
[6] D. Kalyanmoy and S. Ankur, “Solving Bilevel Multi-Ob-
jective Optimization Problems Using Evolutionary Algo-
rithms,” KanGAL Report Number 2008005, 2008.
[7] I. Nishizaki and M. Sakawa, “Stackelberg Solutions to
Multiobjective Two-Level Linear Programming Prob-
lems,” Journal of Optimization Theory and Applications,
Vol. 103, No. 1, 1999, pp. 161-182.
doi:10.1023/A:1021729618112
[8] X. Shi and H. Xia, “Interactive Bilevel Multi-Objective
Decision Making,” Journal of the Operational Research
Society, Vol. 48, No. 9, 1997, pp. 943-949.
[9] A. Messac and C. A. Mattson, “Generating Well Distrib-
uted Sets of Pareto Points for Engineering Using Physical
Programming,” Optimization and Engineering, Vol. 3,
No. 4, 2002, pp. 431-450.
doi:10.1023/A:1021179727569
[10] C. A. Mattson, A. A. Mullur and A. Messac, “Smart
Pareto Filter: Obtaining a Minimal Representation of
Multiobjective Design Space,” Engineering Optimization,
Vol. 36, No. 6, 2004, pp. 721-740.
doi:10.1080/0305215042000274942
[11] S. Sayin, “A Procedure to Find Discrete Representation
of the Efficient Set with Specified Cover Errors,” Opera-
tions Research, Vol. 51, No. 3, 2003, pp. 427-436.
doi:10.1287/opre.51.3.427.14951
[12] H. P. Benson, “An All-Linear Programming Relaxation
Algorithm for Optimizing over the Efficient Set,” Journal
of Global Optimization, Vol. 1, No. 1, 1991, pp. 83-104.
doi:10.1007/BF00120667
[13] Y. Yamamoto, “Optimization over the Efficient Set:
Overview,” Journal of Global Optimization, Vol. 22, No.
1-4, 2002, pp. 285-317. doi:10.1023/A:1013875600711
[14] C. O. Pieume, L. P. Fotso and P. Siarry, “Finding Effi-
cient Set in Multiobjective Linear Programming,” Jour-
nal of Information and Optimization Science, Vol. 29, No.
2, 2008, pp. 203-216.
[15] M. H. Farahi and E. Ansari, “A New Approach to Solve
Multi-Objective Linear Bilevel Programming Problems,”
Journal of Mathematics and Computer Science, Vol. 1,
No. 4, 2010, pp. 313-320.