American Journal of Oper ations Research, 2011, 1, 214219 doi:10.4236/ajor.2011.14024 Published Online December 2011 (http://www.SciRP.org/journal/ajor) Copyright © 2011 SciRes. 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 ValdeMarne, Paris, France Email: calice.oliver.pieume@umontreal.ca, marcotte@iro.umontreal.ca, lpfotso@ballstate.bsu.edu, siarry@univparis12.fr Received July 27, 201 1; revised August 28, 2011; accepted September 10, 2011 Abstract This study addresses bilevel linear multiobjective 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 multiobjective 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, ParetoOptimal 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 [13]. 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 [58]. 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 MultiObjective 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 multiobjective problem issues. The optimistic formulation is considered. We introduced an artificial multiobjective 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 Paretooptimal 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 multiobjective programming problem is presented. Section 4 presents a relation between the feasible set of the upper level deci sions and the Paretooptimal 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 multiobjective programming problem is formulated in
C. O. PIEUME ET AL. 215 general as follows: 12 "min",,, Q xhxh xhxhx , 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 U . Closed pointed convex cones are generally used for the derivation of partial orders in the decision space. Let be an arbitrary cone such that Q R, then the binary relation with respect to the cone (denoted ) is defined by: K ab 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 ondomi nated poi nt is used. Definitio n 1 . A point 0 hU is a nondominated point with respect to the cone if and only if there does not exist a point hUy, 0, such that 0K. If yyy* is a nondominated point with respect to the cone K, then * U, such that is called Paretooptimal (or efficient) solution with respect to the cone * yh x * . The following definition of efficient points is the most used in the literature [911]. Definitio n 2 . A feasible point * U is called Paretooptimal if there does not exist U such that ** * 121 2 ,,,, ,, Q hxhxhxhxhxhx Q and ** * 121 2 ,,,, ,, QQ hxhxhxhxhxhx If * is Paretooptimal, 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 , will be denoted by K ,,EhU and the corre sponding nondominated set denoted by ,, 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; nondominated points corresponding to W do not miss a large portion of W ,, 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 xy y yst gx (BPP) where 1 n XR ; 2 n YR ; ,: 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 resp y are decision variables controlled by the leader (resp the follower). If and are vector value fun ctions Copyright © 2011 SciRes. AJOR
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 xyC xy CxyCxy Ax b xycycycy st yst Ax Ayb (BLMPP) where are 21 ,1,, i Ci m1 nn dimensional constant row vectors; 2i are 2dimensional con stant row vectors; 1 is a pdimensional constant col umn vector and is a qdimensional constant column vector; 1 ,1cib 2 b ,,mn is a constant matrix; 21 pn is a 1 qn constant matrix and 3 a q2 n constant matrix. Let us denote by , the set of rational responses of the follower, for each decision Rx of the leader. It is defined as the Paretooptimal point of the following problem: 2 212 322 min,,,, . nm yR xycycyc y stA ybA x with this notation, one has the following formulation of BLMPP: 1 12 11 min ,,,,,,, Subject to m xX xyC xy CxyCxy Ax b yRx Using also the following representation for the feasible space of BLMPP: 12 11 , and nn yRRAxb yRx One obtains then the following optimistic formulation of BLMPP: 1 12 , min ,,,,,,, . , m xy 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, represents the set defined as follows: 12 11 232 , and nn xyRRAx bAx Ayb It is assumed that is a nonempty 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 multiobjective 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 multiobjective programming problem: 2 12 , 11 232 min,,, ,, . 0, 0 m xy 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 xyf xyfxyfxy st yst gxy (BMPP) (1) Copyright © 2011 SciRes. AJOR
217 C. O. PIEUME ET AL. We introduce now a new relation that could be applied directly. Let us consider the following multiobjective linear programm ing pr o blem: , 11 232 0 min ,0 0 . 0, 0 xy t c 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 cmne is an 11 nn identity matrix. Recall that each i represents the row vector that defined the ithobjective 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 EHZ2030 2 xAyb and 10 1 xb. So, in order to show that , it suf fices to show that 0 z 0 Rx. Let us suppose the con trary. Then there exist such that: 1) 2032 xAyb and 2) 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, ,k0kk cycy . Let now consider the point 0,zxy *, we have: 0 *0 0 0 0 0t t cc xy zI x yex e y and 0 00 00 0 0 0t t cc x 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 HH y y and 0 0 0 x HH y y So 0, y dominate 00 , y 21 mn with respect to the cone , which contradict the fact 21 1 2 \0 mn KR 1 00 , y is a Paretooptimal 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 z dominates z. This im plies that 1 zHz and 1 zHz. Using the structure of the matrix , 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 xI x yex ee yex cy and then 10 10 10 tt cy x ex ex 10 xx This implies that: 0 and 100 t exx , which means that 10 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 Rx. From this theorem, one can deduce that solving our problem (BLMPP’) is equivalent to solve: 1 12 ,,,,, m 2 , min ,, . ,,, xy K xyC xy st xy EHZ C xyCxy (BLMPP”) The theorem led to the following corollary. Corollary 1. 21 ,,,, KK HZSEFE 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 Copyright © 2011 SciRes. AJOR
C. O. PIEUME ET AL. Copyright © 2011 SciRes. AJOR 218 11 232 , 0, 0 t Ax b xAyb xy (LMPP1) The obtained problem consists in an optimization of a linear function over a Paretooptimal 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 [911] can be used. Step 3: Compute the image set of by S YFS. Step 4: Find nondominated points of (called ) with respect to Yeff Y . Step 5: Find the Paretooptimal points set cor responding to . 5.2. Second Approach The second approach could be to generate a representa tive subset of 2 using well known scheme [911], 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 nondominated po ints for the leader. The following algo rithm seems to be natural. ,,K EHZ eff The Paretofilter 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: is a representative subset of the efficient set of BMLPP’, STOP. , 0 min ,0 0 xy t c 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, Paretooptimal 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 nondominated points provided by the last approach (red points). Table 2. Paretooptimal 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 Paretofilter 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 multicriteria concept for the leader. We hope that this research can benefit the development of decision support systems for tackling bilevel multiobjective 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. 235256. doi:10.1007/s1047900701762 [2] J. Fulop, “On the Equivalence between a Linear Bilevel Programming Problem and Linear Optimization over the Efficient Set,” Technical Report WP931, 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. 335358. [4] Y. Yin, “Multiobjective Bilevel Optimization for Trans portation Planning and Management Problems,” Journal of Advanced Transportation, Vol. 36, No. 1, 2000, pp. 93105. doi:10.1002/atr.5670360106 [5] G. Eichfelder, “Multiobjective Bilevel Optimization,” Mathematical Programming, Vol. 123, No. 2, 2008, pp. 419449. doi:10.1007/s1010700802590 [6] D. Kalyanmoy and S. Ankur, “Solving Bilevel MultiOb jective Optimization Problems Using Evolutionary Algo rithms,” KanGAL Report Number 2008005, 2008. [7] I. Nishizaki and M. Sakawa, “Stackelberg Solutions to Multiobjective TwoLevel Linear Programming Prob lems,” Journal of Optimization Theory and Applications, Vol. 103, No. 1, 1999, pp. 161182. doi:10.1023/A:1021729618112 [8] X. Shi and H. Xia, “Interactive Bilevel MultiObjective Decision Making,” Journal of the Operational Research Society, Vol. 48, No. 9, 1997, pp. 943949. [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. 431450. 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. 721740. 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. 427436. doi:10.1287/opre.51.3.427.14951 [12] H. P. Benson, “An AllLinear Programming Relaxation Algorithm for Optimizing over the Efficient Set,” Journal of Global Optimization, Vol. 1, No. 1, 1991, pp. 83104. doi:10.1007/BF00120667 [13] Y. Yamamoto, “Optimization over the Efficient Set: Overview,” Journal of Global Optimization, Vol. 22, No. 14, 2002, pp. 285317. 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. 203216. [15] M. H. Farahi and E. Ansari, “A New Approach to Solve MultiObjective Linear Bilevel Programming Problems,” Journal of Mathematics and Computer Science, Vol. 1, No. 4, 2010, pp. 313320. Copyright © 2011 SciRes. AJOR
