American Journal of Operations Research, 2013, 3, 289-298
http://dx.doi.org/10.4236/ajor.2013.32026 Published Online March 2013 (http://www.scirp.org/journal/ajor)
Generating Efficient Solutions in Bilevel Multi-Objective
Programming Problems
Calice Olivier Pieume1, Patrice Marcotte2, Laure Pauline Fotso3, Patrick Siarry4
1Department of Mathematics, Faculty of Science, University of Yaoundé I, Yaoundé, Cameroon
2Department of Computer Science and Operations Research, University of Montreal, Montreal, Canada
3Department of Computer Sciences, Faculty of Science, University of Yaoundé I, Yaoundé, Cameroon
4LISSI, Faculty of Sciences and Technology, University of Paris XII Val-de-Marne, Créteil, France
Email: olivier.pieume@poledakar.org, marcotte@iro.umontreal.ca,
laurepfotso@ballstate.bsu.edu, siarry@univ-paris12.fr
Received January 2, 2013; revised February 8, 2013; accepted February 17, 2013
ABSTRACT
In this paper, we address bilevel multi-objective programming problems (BMPP) in which the decision maker at each
level has multiple objective functions conflicting with each other. Given a BMPP, we show how to construct two artifi-
cial multiobjective programming problems such that any point that is efficient for both the two problems is an efficient
solution of the BMPP. Some necessary and sufficient conditions for which the obtained result is applicable are provided.
A complete procedure of the implementation of an algorithm for generating efficient solutions for the linear case of
BMPP is presented. A numerical example is provided to illustrate how the algorithm operates.
Keywords: Multi-Objective Programming; Bilevel Programming; Efficient Solution; Efficient Edge; Hierarchical
Systems
1. Introduction
Bilevel programming is proposed in the literature for
dealing with hierarchical systems. It involves two opti-
mization problems where the data of the first one is im-
plicitly determined by the solution of the second. Each
decision maker (DM) tries to optimize its own objective
function without considering the objective of the other
party, but the decision of each party affects the objective
value of the one party as well as the decision space.
Bilevel problems occur in diverse applications, such as
transportation, economics, ecology, engineering and oth-
ers.
Standard bilevel programming problems where each
DM has only one objective have been extensively studied
in the literature [1,2]. Recent books by Dempe [3] and J.
F. Bard [4] present results, applications and solution
methods for standard formulation where the objective
functions and constraints are not necessarily linear.
However, despite their multiple applications [5], the spe-
cial case of bilevel programming problems where each
DM has more than one objective function has not yet
received a broad attention in the literature. We have
found only about a dozen articles related to this class of
problems in the literature [6-11]. The lack of work is due
certainly to the difficulty of searching and defining opti-
mal solutions. Contrarily to the standard two levels pro-
gramming problem where it is usually assumed that the
set of rational responses of the follower is a singleton, in
the bilevel multi-objective problem, the lower level op-
timization problem has a number of trade-off optimal
solutions and the task of the upper level is to focus its
search on multiple trade-off solutions which are members
of optimal trade-off solutions of lower level optimization
problem. Bilevel Multi-objective Programming Problem
is then computationally more complex than the conven-
tional Multi-Objective Programming Problem or a bilevel
Programming Problem.
In this paper, we address bilevel multi-objective prob-
lems in which the decision maker at each level has mul-
tiple objective functions conflicting with each other.
Given a BMPP, we show how to construct two artificial
multi-objective programming problems such that any
point that is efficient for both the two problems is an ef-
ficient solution of the BMPP. Based on this result, we
provided a general algorithm for generating efficient so-
lutions of BMPP. A complete procedure of its imple-
mentation for the linear case of BMPP is presented. A
numerical example is provided to illustrate how the algo-
rithm operates.
The paper is organized as follows. In the next section,
in addition to some notations and definitions that are
given, we present the formulation of the problem on
C
opyright © 2013 SciRes. AJOR
C. O. PIEUME ET AL.
290
which we will focus. In Section 3, we show how to con-
struct two artificial multi-objective programming prob-
lems whose resolutions can permit to generate efficient
solutions of BMPP . Section 4 provides some necessary
and sufficient conditions for the application of the ob-
tained relation. Section 5, is devoted essentially to the
implementation of the algorithm for the generation of
efficient points in bilevel linear multi-objective pro-
gramming problems. We give in Section 6 a numerical
example to illustrate the proposed algorithm. Finally, the
paper is concluded in Section 7.
2. The Bilevel Multi-Objective Programming
Problem (BMPP)
2.1. Preliminaries and Notations
A multi-objective programming problem is formulated in
general as follows:
“min”
 
12
hxh xh
 

,,,
Q
xh x
.
s
tx U
:hR R
R
(MO P P)
where nQ
is the objective function vectors and
the set of constraints.
n
In order to solve (MOPP), it is necessary to define
how objective function vectors
U
 

,,,
Q
xh x
12
hxh
should be compared for different alternatives
x
U
. So
one must define on
hU
Q
R
the order that should be used
for the comparison. Due to the fact that, for , there
is no canonical (total) order in as there is on R, one
can just define partial orders on
Q2
hU
KQ
R. Let K be an ar-
bitrary cone such that , a binary relation with
respect to the cone K (noted K) can be defined by:
K
abaK

yhU

b if and only if
Partial orders introduced by closed pointed convex
cones are the most used. Due to the fact that it could not
be possible to find a solution that optimize simultane-
ously all the objective functions, a weaker concept, the
concept of Non-dominated point is used.
Definiti o n 1
A point 0is a Non-dominated point with re-
spect to the cone K if and only if there does not exist a
point
y
hU, 0 such that 0. If 6yKyy
yy
is
a non-dominated point with respect to the cone K, then
x
U
such that
y
hx

is called Pareto-optimal
point with respect to the cone K.
The following definition of efficient points is the most
used in the literature [12-15].
Definitio n 2
A feasible point
x
U
is called Pareto-optimal if
there does not exist
x
U



,
,,,
Q
Q
h x
h x
such that
 
 
12
12
,,hxhx
hx hx

and

 

12
12
,,,
, ,,.
Q
Q
hxhxh x
hxhxh x
 
If
is Pareto-optimal then is called Non-
dominated point.

hx
The efficient (or Pareto optimal) solutions are then so-
lutions that cannot be improved in one objective function
without deteriorating their performance in at least one of
the rest. Let us remark that Definition 2 is a particular
case of Definition 1 where the cone used is
\0Rq

Q
Solving a multi-objective optimization problem con-
sists in finding a part or the whole set of efficient points
and to present it for evaluation to the Decision maker
(DM). The choice of the DM is then considered as the
optimal solution of the multi-objective optimization
problem.
.
2.2. The Optimistic Formulation of BMPP
A standard Bilevel Programming Problem (BPP) can be
formulated as follows:


0
min ,
min,subject tosolves
.,0
yY
xX
Gx
fxy
Fxy yst gxy

(BPP)
12
,, :,
nn
FxX RyRXYY
f
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; Gg are inequality
constraints. The decision variable of the leader is x and
that of the inner problem is y.
F
When the objective functions f and the con-
straints
,Gg of the upper-level and lower-level prob-
lems are all linear, the resulting problem is called Bilevel
Linear Programming Problem (BLPP) or Linear Stack-
elberg Game.
If F and f are vector value functions
12 1122
:and:
nn mnn m
FRRR fRRR 
 
, then one
speak of bilevel multi-objective programming problems
(BMPP). The formulation of a bilevel multi-objective
programming problem (BMPP) can be given as follows:

 


1
2
1
1
min,,, ,,
0
min,,,,,
.solves
.,0
m
xX
m
yY
FxyFxyFxy
Gx
fxyfxyf xy
st ystgxy

(BPP)
Let us denote by Rx, the set of rational responses
of the follower for each decision x of the leader, it is de-
Copyright © 2013 SciRes. AJOR
C. O. PIEUME ET AL. 291
fined as the set of Pareto-optimal points of the following
problem:
 

2
1
min,,, ,,
m
yY fxyfxyf xy

., 0stgxy


1
, ,
m
With this notation, we have the following formulation
of BMPP:
 


1
min,,,
0
subject to
xX
F
xyF xy
Gx
yRx
F xy
Let denote by the feasible space of BMPP defined
by:
 
and
12
,0
nn
x
yRRGx

 yRx


1
, ,
m
The optimistic formulation of BMPP is given by:
 

1
,
min,,,
subject to,
xy
F
xyF xy
xy

F xy
(BMPP’)
The following definition holds.
Definitio n 3
,
x
y

is an efficient solution of BMPPif and only
if
,xy

a nd
,xy
 


,
,,,,
xy
such that


12
12
,, ,,,
,,
FxyFxy
F
xy Fxy
 
xy





,
,,,,
xy
and


12
12
,, ,,,
,,
F xyFxy
F
xy Fxy
 
xy

The main goal of this paper is to present an approach
for generating efficient points of BMPP’.
Throughout the rest of the paper, the set of efficient
point of a multi-objective optimization problem defined
by a vector value function h on a feasible set U with re-
spect to a cone K will be noted:
,,EhU

1
1
\0
mm
KR
K. If one
speaks of efficient point without making a reference to a
cone, it is will be with respect to Definition 2. We con-
sider also the following notations: ,
1

2\0
mm
KR
2
2, 1
m
X
R
YR, ,
2
m
 

0and
12
,/
nn
Z
xyR GxR

y Rx
and S denotes the whole set of efficient solutions of prob-
lem BMPP’.
3. Generating Efficient Points for BMPP
Let us consider the following multi-objective program-
ming problem, constructed from the data of (BMPP’):
 

1
,
min,,,,
.,
xy fxy fxy
stxyZ
Let 2
21
3\0 0
mmn
KR
 and be as defined
above.
Theorem 1: 3
K
Proof: It is a slight modified version of Theorem 4.1
given in [7].
,,EeZ
Solving (BMPP’) is then equivalent to solve the prob-
lem:



2, ,
m
f xyx
(MPP2)

2
3
1
min,,, ,,
., ,,
m
xX
K
F
xyFxyFxy
stxyEfZ

(1)
This leads naturally to the following corollary:
Corollary 1

31
,,,,
KK
EfZSEF .
Finding 3
K
,,EfZ
is not an easy task for at least
two reasons: First, it is difficult to generate the whole
efficient set 3
,,K
EfZ because it can be infinite and
secondo, in the literature there does not exist approaches
developed for finding efficient points with respect to the
specific cone
2
1
\0 0
mn
KR
2
3m. Methods are usu-
ally for cones defined in the form
\0 ,
n
RnN
n.
21
421
\
mn
Rmn
K
. The following result holds. Let
Theorem 2

43
,, ,,
KK
EfZ EfZ 

Proof:
Let 4
,,,K
EfXx Zy then there does not
exist
,
X
xy

such that
21
21
\
mn
fXfXRm n
 (1). Since

221
21 21
\0 0\
mmn
mn
RRmn


(1) there does
not exist
, xy
X

such that
 
 
2
21
\0 0
mmn
fXfX R
 
. Consequently,
3
,,,K
EfXx Zy. Therefore, one can conclude
that
43
,, ,,
KK
EfZEfZ
T
.
heorem 2 suggests capturing a subset of
3
,,K
EfZ by solving the following problem:
 


1
4
1
min,,, ,,
., ,,
m
xX
K
F
xyFxyFxy
stxyEfZ

(BMPP”)
This formulation and Corollary 1 lead obviously to the
following result:
Corollary 2
,,,,ZEfFE S

41
KK
Even if the cone used in this last formulation has the
desired representation
.
\0 ,
n
RnN
n
, optimizing
multi-objective functions over an efficient set could not
be an easy task. We introduce a new problem easier to
solve and whose resolution could permit to capture a
subset of efficient solutions of (BMPP”).
Let consider the following multi-objective program-
Copyright © 2013 SciRes. AJOR
C. O. PIEUME ET AL.
292
ming problem:
 

1
min,,,
.,
xX


1
, ,
m
F
xyF xy
stxyZ
F xy
(MPP1)
Theorem 3



41
41
,,
,,
KK
KK
EFZ

,,
,,
EZ
EF
f
ZfE
Proof:
Let


41
,,
KK
EFfZ,,,xy EZ, then

4
,xy,,
K
E Zf


1
,,,
K
xy EFZ and. Let us
suppose that



41
,,
KK
Z
,,xyE f. Then there
exist
,
x
y
that dominates
,
x
y with respect to the
problem MPP1 and the cone K1, which means
1
,,
K
F
xy

Fxy. This implies that:

,
4
,
K
EfZ

,xy such that
,,
F
xy Fxy

,
and

,
F
xy F xy. Since

4
,,K
Z Z
,
Ef
, it
implies that
x
yZ
 such that

,,
F
xyFxy and

,,
F
xyFxy
. Conse-
quently . Contradiction with the

1
,,,
K
xy EFZ

fact that

KK
Z
41
,,EF,,,E fZxy.
The following result is deducted from Theorem 3 and
Corollary 2:
Corollary 3

,, ,,EfZ EFZS
41
KK
This last result stipulates that in order to find efficient
points of BMPP, one can just solve problem MPP1 (with
respect to 1
.
) and problem MPP2 (with respect to
4
K
) and retain all efficient points that are in the both
solutions sets.
4. On the Implementation of an Algorithm
In order to implement the above results, one must be sure
that the algorithm will generate at least one efficient so-
lution to BMPP. This condition is fulfilled if and only if

,, ,,EfZ EFZ
41
KK
. A necessary condition
is that each of the two sets,
4
K and ,,EfZ
1
K must be different from empty set. The
following result gives sufficient conditions for it.
,,EFZ
Theorem 4 If the following three conditions hold:
1) Z is nonempty and compact set;
2)
1
1, ,im
, F is lower semicontinuous;
j
3)
2
1, ,jm
1
m
R
1
m
R
, fj is lower semicontinuous.
Proof:
If 2) holds, then F is -semicontinuous (i.e. the
pre-image of the translated negative octant is always
closed). Since from 1) Z is nonempty and compact, F(Z)
is -semicompact and nonempty. Based on this result,
Theorem 2.8 of [13] permits then to say that the set of
Non-dominated points is non-empty. Which permits to
conclude that the set of Pareto-points is nonempty i.e.
1
,,K
EfZ. A similar proof permits to conclude
also that
4
,,K
EfZ.
12
nn
ZR
The following theorem gives a sufficient condition for
the implementation of an algorithm based on our last
result (Corola rry3).
Theorem 5 If the following two conditions hold:
is nonempty and compact set. 1)
1,,1 ,1,,2 ,0imjm
2) 00
 such that
0i
F
and 0j
f
are lower semicontinuous functions;
0i
F
and 0j
f
are injective functions;
00ij
F
f
;
Then
41
,, ,,
KK
EfZ EFZ


min ,
.
Proof:
Let us suppose that 1) and 2) hold. Consider the fol-
lowing optimization problem: 0j
f
zzZ
(pb1).
Since fj0 is a lower semicontinuous function and Z is a
nonempty compact set, pb1 has at least one optimal solu-
tion, z0 (in fact z0 is unique).
We claim that
 
41
0,, ,,
KK
zEfZEFZ.
1) Let us first show that

4
0,,K
zEfZ. Suppose
that
4
0,,K
zEfZ0
,zZzz , then there exists
0


such that zfz
f
and
f
0
zfz
. This im-
plies that
000jj
f
zfz

. Due to the fact that z0 is an
optimal solution of (pb1), we have then
000jj
f
zfz
0
.
Since fj0 is an injective function, this implies that z = z.
Contradiction. Consequently

0,,zEfZ
00ij
4
K
2) Since
.
and 0
F
af
, z0 is also an optimal
solution of
min ,
0i
F
zzZ

1
,,K
zEFZ
. With a similar proof as
in 1), one obtains that .
0
Combining 1) and 2) leads to
41
0,, ,,
KK
zEfZEFZ. Hence,
41
,, ,,
KK
EefZ EFZ
If the preceding conditions are fulfilled, then one can
think of the implementation of an algorithm to generate
efficient points of BMPP based on Corollary 3. At least
two ideas can be used. The first could be to generate the
whole set of efficient points of MLPP1 and then iterate
on the set in order to retain the ones that are also
Pareto-optimal for the second problem (MLPP2). But it
would be a difficult task to generate the whole efficient
set of MLPP1 [14-16].
The second idea could be to generate progressively (as
we go along) efficient points for MPP1 and test simulta-
neously their efficiency for MLPP2 before moving to
another efficient point of MPP1. This seems to be more
practical. An algorithm based on the last idea can be
formulated as follows:
Copyright © 2013 SciRes. AJOR
C. O. PIEUME ET AL. 293
Algorithm 1 /*Computational steps of the algo-
rithm*/
1) Read problem data and construct problem MPP1
and MPP 2.
2) Generate an efficient solution (lets z) of problem
MPP1, go to step 4.
3) Generate a new efficient solution z of problem
MPP1.
4) If z is efficient solution of MPP2 then z is solution
of MBPP; .

:SS z
5) If the number of points in S is sufficient or all the
efficient points of MPP1 are tested then stop Otherwise
go to step 3.
We present in the following section how it can be ef-
fectively implemented for generating efficient solutions
for linear bilevel multi-objective programming problems.
5. Generating Efficient Points in Bilevel
Multi-Objective Linear Programming
Problems
Problem and Notations
We consider the following problem:
 

1
1
2
1
11
1
232
min,,,,,
.solvesmin ,,
.
n
n
m
xR
yR
FxyCxyCxy
Ax b


1
,, ,
m
s
tyfxycxy
st AxAxb

c xy

1
, ,
m
(BLMPP)
The two multi-objective problems used in our preced-
ing algorithm are:
 
11
11
232
min,, ,
.
0, 0
n
xR
F
xyC xy
Ax b
st AxAxb
xy


C xy
(LMPP1)
And
 
1
,
11
232
min,, ,
.
0, 0
xy

1
,, ,
m
f
xyc xy
Ax b
st AxAxb
xy


cxyx
2
n
yR
(LMPP2)
Given and
1
n
xR
12
nn
zR
1
,
n
, it will be convenient to
introduce the vector whose first n1 compo-
nent are 12
,,
x
x
,yx
12 2n
and last n2 components are
,,yy.
We call C (resp c) the matrix such that


12 1
,,, resp
m
F
zCzCzCzCz fzcz
,,,,zz z
.
In order to be more concise, the notations and results that
follow now are with respect to LMPP1, but all are also
valid for (LMPP2).
After adding p + q non negative variable
12 2pqpqp q the data of (LMPP1) can be
represented by the following tableau:
Z
N ZB
(T): D C 0
b A I
1
23
0
A
where A
A
A



1
2
b
bb



and .
The algorithm will start with an initial efficient ex-
treme point and will iterate through different efficient
extreme points of LMPP1. At any iteration, for every
unexplored efficient extreme point z of LMPP1, the effi-
ciency with respect to LMPP2 is tested.
Points that are Pareto-optimal for both the two prob-
lems will be then retained. The entire scheme is repeated,
until all the efficient extreme solutions of LMPP1 are
tested.
Since efficient extreme points form a connected graph
and that Z is regular, LMPP1 has a finite number of ex-
treme efficient points, and so the algorithm is bound to
terminate in a finite number of steps.
At each iteration of the algorithm, the current efficient
(extreme) point z* will be always associated with a tab-
leau T (as presented above). NT will denote the nonbasic
set of the current efficient point z* associated to a tableau
T. S1 will represent the set of Pareto-optimal points of
problem LMPP1 that the efficiency with respect to
LMPP2 has to be tested. S2 will represent the set of
points that have been discovered to be Pareto-optimal to
both the two problems.
The result below [16-18] is the scheme that will be
used to check if a feasible solution is a Pareto-optimal
solution.
Lemma 1 A point z0 in Z is Pareto-optimal for prob-
lem (LMPP1) if and only if the solution
,zs
0
,0
max e.
t
zZs
of the
following linear program yields a maxim um value zero:
s
stCz IsCz
 
If the maximum value is not zero, then z is Parto-op-
timal (with respect to (LMPP1)).
The following result [16] can be used to determine in-
cident efficient edges.
Lemma 2 The edge incident to the current efficient
Copyright © 2013 SciRes. AJOR
C. O. PIEUME ET AL.
294
extreme point obtained by increasing the nonbasic vari-
able
N
j
z
0
N
j
has a solution
wth
is efficient if an only if the system

,0
Nt
N
CvwC e
vw wi
  (2)
provided the pivot in the
N
j
z column has a pivot row
with bi > 0. If the pivot row has bi = 0 and aij < 0 for
some j, then the edge obtained by pivoting by the mini-
mum ratio rule in the
N
j
z
Nt
vIwCe
column is efficient if and only
if (2) holds.
Based on this lemma, Song [18] claims that this test
for each edge can be implemented by solving the fol-
lowing linear program:
,0
.max
N
Nt
j
vw stwC
If the optimal value is zero, then the corresponding
edge is efficient.
It is the scheme that will be used by our algorithm for
finding efficient edges. Based on these results, the algo-
rithm can be reformulated as follows.
Algorithm 2 /*Computational steps of the algo-
rithm*/
1) Read data of problem BLMPP and construct prob-
lems LMPP1 and LMPP2.
2) Find an arbitrary feasible element z0 Z.
3) With z0, construct and solve the following proble
m
(in order to find an initial efficient point to LMPP1)
0, 0,zZ s max e.
tsstCzIsCz (test0)
Let

,zs

1
:Sz
the optimal solution of (test0). If the op-
timum value of (test0) is 0, then z0 is efficient,
. Otherwise, z is efficient,
0

:Sz
S

:\SSz
,, 0zzZs
 
1
4) If 1, stop. Otherwise, take an element z*
from S1 and .
.
11
5) Test if z* is efficient for LMPP2 by solving the
following problem:
max e.
tsstczIsce (test1)
Let

,,,zs xys

2SSz
the optimal solution of (test1).
If the optimal value of (test1) is 0 then z* is efficient to
LMPP2 and hence is a solution of (BLMPP):
.
2:
If the number of efficient point is sufficient, the
n
stop.
6) Find efficient edges (with respect to LMPP1) inci-
dent to z*, by solving for each j NT the following
problem:
.max NtN
wCvIst w ,,0
tN
jj
Ce v w (3)
Let denote by
J
TNT the set of j such that the
optimal value of PBj is zero. (Let us recall that the edge
obtained by increasing the nonbasic variable
N
j
z in
T
is efficient if and only if jJT
.)
For each jJT
, generate efficient points incident to
z* by making a pivot operation on the column j + 1 o
f
tableau T. Let denote by ST the set of efficient points
incident to the current efficient point z* that have no
t
already been tested. 1: 1SSST. Go to step 4.
6. Illustrative Example
Let us consider finding an efficient solution to the fol-
lowing problem:
131312
12212
1312 3
3
123 3
min 22
1,2, 0,0
1
min, 22
2
solves
,
4, 0
,xxxxxx
xx xxx
x
xxx x
x
xxx x


 
 


(BLMPP)
At Step 1: The following two problems are con-
structed:
121313
12 2
123
123
min2 ,2 ,
1, 2
subject to4
0,0, 0
x
xx xxx
xx x
xxx
xxx
 

 

(LMPP1)
And
1312 312
12 2
123
123
1
min, 22,,
2
1, 2
subject to4
0,0, 0
x
xxxxxx
xx x
xxx
xxx
 


 


0, 0,0zZ
123
121
132
133
12 2
123
123123
max
20
20
0
subject to1, 2
4
0,0,0, 0,0,0
sss
xxs
xxs
xxs
xx x
xxx
xxxsss

 
 
  




(LMPP2)
At step 2: We start with .
0
At step 3: The following problem is constructed in
order to find an initial efficient extreme point (with re-
spect to LMPP1):
(test0)
The initial simplex tableau of the problem is:
Copyright © 2013 SciRes. AJOR
C. O. PIEUME ET AL. 295
Copyright © 2013 SciRes. AJOR
0 0 0 0 0 0 0 1 11
0 1 2 0 0 0 0 1 0 0
0 1 0 2 0 0 0 0 1 0
0 1 0
1
0 0 0 0 0 1
1 1 1 0 1 0 0 0 0 0
2 0 1 0 0 1 0 0 0 0
4 1 1
1 0 0 1 0 0 0
The optimal simplex tableau of the problem is:
2 1 0 1 2 0 0 0 0 0
2 1 0 0 2 0 0 1 0 0
0 1
0 2 0 0 0 0 1 0
0 1 0 1
0 0 0 0 0 1
1 1 1 0 1 0 0 0 0 0
1 1 0 0 1
1 0 0 0 0
5 2 0 1 1 0 1 0 0 0
The solution of the problem is

0,1,zs
 

, 0,20,0,
and the optimal value of the
problem is 2. Since the value is different from 0,
0 is not an efficient point (to LMPP1). We
deduct from this optimal tableau that
0, 0, 0z

0,1, 0z is an
efficient extreme point (to LMPP1) and the correspond-
ing efficient tableau is given by (T1):
2 1 0 0 2 0 0
0 1 0 2 0 0 0
0 1 0 1
0 0 0
1 1 1 0 1 0 0
1 1 0 0 1 1 0
5 2 0 1 1 0 1


10,1,0
1S
SoS .
At step 4: Since , we take 
0,1,0
1
and re-
move it from (so S). 1S
At Step 5: We must test if
0,1,0 is efficient to
MLPP2 by solving the following problem:
1234
131
12 32
13 24
12 2
123
12 31
max
10
2
221
0, 1
subject to
1, 2
4
0,0,0, 0,0,
ssss
xxs
xx xs
xs xs
xx x
xxx
xxxss





 


234
0, 0ss
(test1)
The optimal simplex tableau of this problem is:
2 2.52 3 0 0 0 0 0 0 0
0 0.50 1 0 0 0 1 0 0 0
1 2 1 2 0 0 0 0 1 0 0
0 1 0 0 0 0 0 0 0 1 0
1 0 1 0 0 0 0 0 0 0 1
2 0 1 0 0 1 0 0 0 0 0
4 1 11 0 0 1 0 0 0 0
Since the optimal value is 2, so different from zero,
0 is not efficient to LMMP2. We continue to
step 6.
1,0, 1z
At step 6: We use T1 to find incident edge to
0. Here the set of non-basis variables is given
by
1,0, 1z
1, 3,4NT
123 1
13
23 14
–1
22
maxsubject to
21
,0
N
N
N
jN
N
vvvw
vw
wvvw
vw

 
 
1. We solve for different j in NT1 the
problem (PBj) as presented in the algorithm. For j = 1,
PB1 is:
(PB1)
The optimal value is 0. With the same manner, for j =
3, the optimal value of PB3 is 2; for j = 4, the optimal
value of PB4 is 0. So
1
At step 7: Only j = 1 led to a new efficient extreme
point. The new efficient point obtained is
1, 4JT
. We go to step 7.
1, 0,0 with
the corresponding tableau given by (T2):
1 0 1 0 1 0 0
1 0 1 2 1 0 0
1 0 1 1 1 0 0
1 1 1 0 1 0 0
2 0 1 0 0 1 0
3 0 2 1 1 0 1
The set of nonbasic variables is given by
22,3,4NT


1, 0, 0ST
. One has then 1 and hence
11, 0, 0S
1
S
. We go again to step 4.
At step 4: Since
, we take
1, 0, 0
S and re-
move it from S1 (so 1
). We go to step 5.
At step 5: We must test if
1, 0, 0 is efficient to
MLPP2 by solving the following problem:
C. O. PIEUME ET AL.
296
1234
131
12 32
132 4
12 2
123
12 31
max
11
22
222
1, 2
subject to
1, 2
4
0,0,0, 0,0,
ssss
xxs
xx xs
xs xs
xx x
xxx
xxxss


 
 



234
0, 0ss
(test1)
The optimal value of this problem is 0, so
1, 0,0


1, 0, 0

1, 0, 0z
is
efficient to LMPP2 and hence is an efficient solution to
our problem: . We continue to step 6.
2
At step 6: We find efficient extreme points incident to
our current efficient point (Using T2 and
NT2) by solving for each j in NT2 the problem (PBj). For
j = 2, one obtains 2 as optimal value of PB2; for j = 3 the
optimal value of PB3 is 0; for j = 4, the optimal value of
PB4 is 2. So
S
23JT . We go to step 7.
At step 7: j = 3 leads to a new efficient extreme point
with the corresponding tableau T3:

1, 0, 3
1 0 1 0 1 0 0
5 0 5 0 3 0 2
2 0 3 0 2 0 1
1 1 1 0 1 0 0
2 0 1 0 0 1 0
3 0 2 1 1 0 1
The set of nonbasic variables is given by
. One has then
32, 4, 6NT
2 and hence
1, 0, 3
ST
11, 0, 3S. We go again to step 4.
At step 4: Since , we take
1
S
1, 0, 3
S
and re-
move it from S1 (so ). We go to step 5.
1
At step 5: We must test if
1, 0, 3 is efficient to
MLPP2 by solving the following problem:
1234
131
12 32
132 4
12 2
123
12 31
max
15
22
228
1, 0
subject to
1, 2
4
0,0,0, 0,0,
ssss
xxs
xx xs
xs xs
xx x
xxx
xxxss


 
 



The optimal value of this problem is 11.5, so 1, 0,3
is not efficient for LMPP2 and hence is not a solution to
our problem. We continue at step 6.
At step 6: We find efficient extreme points incident to
the current efficient point
1, 0, 3z by solving for
each j in NT3 the problem
j. For j = 2, the optimal
value of the problem PB2 is 2. For j = 4 and j = 6, the
optimal values of the obtained problems are 0 and so
PB
3
At step 7: One finds that it is only j = 4 that leads to a
new efficient extreme point
4, 6JT
. We go to step 7.
0, 0, 4with the corre-
sponding tableau T4:
0 0 1 2 0 0 0
8 3 2 0 0 0 2
4 2 1 0 0 0 1
1 1 1 0 1 0 0
2 0 1 0 0 1 0
4 1 1
1 0 0 1
The set of nonbasic variables is given by
41, 2,6NT


0, 0, 4ST
. Thus 4 and hence
10, 0, 4S
1
S
. We go again to step 4.
At step 4: Since

0, 0, 4
S, we take and re-
move it from S1 (so
234
0, 0ss
(test1)
1

0, 0, 4
). We go to step 5.
At step 5: We must test if is efficient to
MLPP2 by solving the following problem:
12 34
131
12 32
13 24
12 2
123
1231234
max
14
2
228
0, 0
subject to
1, 2
4
0,0,0,0, 0,0, 0
ssss
xxs
xx xs
xs xs
xx x
xxx
xxxssss


 
 




(test1)
The optimal value of this problem is 12, so
0, 0, 4
is not efficient for LMPP2 and hence is not a solution to
our problem. We continue at step 6.
At step 6: We find efficient extreme points incident to
the current efficient point
0, 0, 4Z
by solving for
each j in NT4 the problem (PBj). For all j in NT4, 0 is the
optimal value of PBj. So
4
At step 7: One finds that only j = 2 leads to a new ef-
ficient extreme point
1, 2,6JT. We go to step 7.
0,1,5 with the corresponding
tableau T5:
Copyright © 2013 SciRes. AJOR
C. O. PIEUME ET AL. 297
2 1 0 0 2 0 0
10 5 0 2 0 0 2
5 3 0 0 1 0 1
1 1 1 0 1 0 0
1 1 0 0 1 1 0
5 2 0 1 1 0 1
The set of nonbasic variables is given by
5
NT
1, 4,6
. So 5 and hence
ST
0, 1,5
1
0,1,5 S
S. We go again to step 4.
At step 4: Since 1, we take 
0,1,5
S
and remove
it from S1 (so ). We go to step 5.
1
At step 5: We test if
0,1,5 is efficient to MLPP2
by solving the following problem:
1234
131
12 32
13 24
12 2
123
12 31
max
15
2
2211
0, 1
subject to
1, 2
4
0,0,0, 0,0,
ssss
xxs
xx xs
xs xs
xx x
xxx
xxxss





 


234
0, 0ss
(test1)
The optimal value of this problem is 17.
0,1,5S
o is
not efficient for LMPP2 and hence is not solution to our
problem. We continue at step 6.
At step 6: We find efficient extreme points incident to
the current efficient point
0,1,5z
by solving (PBj)
for each j in NT5.
For j = 1, 1.5 is the optimal value of PB1; for j = 4 the
optimal value of PB4 is 2; for j = 6, the optimal value of
PB6 is 0. So
5
At step 7: j = 6 leads to an efficient extreme point al-
ready tested (that is
6JT
. We go to step 7.
0,1,0


1, 0, 0
). We go to step 4.
At step 4: S1 is empty and the algorithm stops.
Since 2, we deduce that
S
1, 0, 0 is an
efficient solution to the bilevel linear multi-objective
programming problem considered.
7. Conclusion
We have presented in this paper the optimistic formula-
tion of a bilevel multi-objective programming problem.
We have derived two multi-objective programming prob-
lems such that any point that is efficient for both the two
problems is an efficient solution of the BMPP. An algo-
rithm to generate efficient solutions for BMPP has been
developed and applied to the resolution of the linear case
of BMPP. We have also provided a necessary and a suf-
ficient condition for which the proposed algorithm is
applicable. Further studies for finding less restrictive
conditions is going on. The performance of the algorithm
proposed could be significantly improved on larger prob-
lems if a better way to generate efficient points for multi-
objective programming problems were used. We hope
that this study will contribute in spurring more interest
bilevel multi-objective optimization from other research-
ers and practitioners in the field of Mathematical Pro-
gramming.
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] 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.
[3] S. Dempe, “Foundations of Bilevel Programming,” Klu-
wer Academic Publishers, Dordrecht, 2002.
[4] J. F. Bard, “Practical Bilevel Optimization,” Kluwer Aca-
demic Publishers, Dordrecht, 1998.
[5] 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
[6] H. Bonnel and J. Morgan, “Semivectorial Bilevel Opti-
mization Problem: Penalty Approach,” Journal of Opti-
mization Theory and Applications, Vol. 131, No. 3, 2006,
pp. 365-382. doi:10.1007/s10957-006-9150-4
[7] G. Eichfelder, “Multiobjective Bilevel Optimization,”
Mathematical Programming, Vol. 123, No. 2, 2008, pp.
419-449. doi:10.1007/s10107-008-0259-0
[8] D. Kalyanmoy and S. Ankur, “Solving Bilevel Multi-
Objective Optimization Problems Using Evolutionary Al-
gorithms,” In: Proceedings of the 5th International Con-
ference on Evolutionary Multi-Criterion Optimization,
Springer-Verlag Berlin, Heidelberg, 2008, pp. 110-124.
[9] I. Nishizaki and M. Sakawa, “Stackelberg Solutions to
Multiobjective Two-Level Linear Programming Problems,”
Journal of Optimization Theory and Applications, Vol.
103, No. 1, 1999, pp. 161-182.
doi:10.1023/A:1021729618112
[10] X. Shi and H. Xia, “Interactive Bilevel Multi-Objective
Decision Making,” The Journal of the Operational Re-
search Society, Vol. 48, No. 9, 1997, pp. 943-949.
[11] X. Shi and H. Xia, “Model and Interactive Algorithm of
Bi-Level Multi-Objective Decision-Making with Multiple
Interconnected Decision Makers,” Journal of Multi-Cri-
teria Decision Analysis, Vol. 10, No. 1, 2001, pp. 27-34.
doi:10.1002/mcda.285
[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.
Copyright © 2013 SciRes. AJOR
C. O. PIEUME ET AL.
Copyright © 2013 SciRes. AJOR
298
doi:10.1007/BF00120667
[13] M. Ehrgott, “Multicriteria Optimisation,” Springer, Berlin,
2000.
[14] H. Iserman, “The Enumeration of the Set of All Efficient
Solutions for a Linear Multiple Objective Program,” Op-
erational Research Quarterly, Vol. 28, No. 3, 1977, pp.
711-725.
[15] C. O. Pieume, L. P. Fotso and P. Siarry, “Finding Effi-
cient Set in Multiobjective Linear Programming,” Journal
of Information and Optimization Science, Vol. 29, No. 2,
2008, pp. 203-216.
[16] J. G. Ecker, N. S. Hegner and I. A. Kouada, “Generating
All Maximal Efficient Faces for Multiple Objective Lin-
ear Programs,” Journal of Optimisation Theory and Ap-
plications, Vol. 30, No. 3, 1980, pp. 353-381.
doi:10.1007/BF00935493
[17] Y. Yamamoto, “Optimization over the Efficient Set: Over-
view,” Journal of Global Optimization, Vol. 22, No. 1-4,
2002, pp. 285-317. doi:10.1023/A:1013875600711
[18] J. G. Ecker and J. H. Song, “Optimizing a Linear Func-
tion over an Efficient Set,” Journal of Optimization The-
ory and Applications, Vol. 83, No. 3, 1994, pp. 541-563.
doi:10.1007/BF02207641