Generating Efficient Solutions in Bilevel Multi-Objective Programming Problems

Affiliation(s)

Department of Mathematics, Faculty of Science, University of Yaoundé I, Yaoundé, Cameroon.

Department of Computer Science and Operations Research, University of Montreal, Montreal, Canada.

Department of Computer Sciences, Faculty of Science, University of Yaoundé I, Yaoundé, Cameroon.

LISSI, Faculty of Sciences and Technology, University of Paris XII Val-de-Marne, Créteil, France.

Department of Mathematics, Faculty of Science, University of Yaoundé I, Yaoundé, Cameroon.

Department of Computer Science and Operations Research, University of Montreal, Montreal, Canada.

Department of Computer Sciences, Faculty of Science, University of Yaoundé I, Yaoundé, Cameroon.

LISSI, Faculty of Sciences and Technology, University of Paris XII Val-de-Marne, Créteil, France.

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 artificial 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.

Cite this paper

C. Pieume, P. Marcotte, L. Fotso and P. Siarry, "Generating Efficient Solutions in Bilevel Multi-Objective Programming Problems,"*American Journal of Operations Research*, Vol. 3 No. 2, 2013, pp. 289-298. doi: 10.4236/ajor.2013.32026.

C. Pieume, P. Marcotte, L. Fotso and P. Siarry, "Generating Efficient Solutions in Bilevel Multi-Objective Programming Problems,"

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,” Kluwer Academic Publishers, Dordrecht, 2002.

[4] J. F. Bard, “Practical Bilevel Optimization,” Kluwer Academic Publishers, Dordrecht, 1998.

[5] Y. Yin, “Multiobjective Bilevel Optimization for Transportation 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 Optimization Problem: Penalty Approach,” Journal of Optimization 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 MultiObjective Optimization Problems Using Evolutionary Algorithms,” In: Proceedings of the 5th International Conference 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 Research 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-Criteria 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. 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,” Operational Research Quarterly, Vol. 28, No. 3, 1977, pp. 711-725.

[15] C. O. Pieume, L. P. Fotso and P. Siarry, “Finding Efficient 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 Linear Programs,” Journal of Optimisation Theory and Applications, Vol. 30, No. 3, 1980, pp. 353-381. doi:10.1007/BF00935493

[17] 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

[18] J. G. Ecker and J. H. Song, “Optimizing a Linear Function over an Efficient Set,” Journal of Optimization Theory and Applications, Vol. 83, No. 3, 1994, pp. 541-563. doi:10.1007/BF02207641

[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,” Kluwer Academic Publishers, Dordrecht, 2002.

[4] J. F. Bard, “Practical Bilevel Optimization,” Kluwer Academic Publishers, Dordrecht, 1998.

[5] Y. Yin, “Multiobjective Bilevel Optimization for Transportation 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 Optimization Problem: Penalty Approach,” Journal of Optimization 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 MultiObjective Optimization Problems Using Evolutionary Algorithms,” In: Proceedings of the 5th International Conference 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 Research 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-Criteria 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. 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,” Operational Research Quarterly, Vol. 28, No. 3, 1977, pp. 711-725.

[15] C. O. Pieume, L. P. Fotso and P. Siarry, “Finding Efficient 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 Linear Programs,” Journal of Optimisation Theory and Applications, Vol. 30, No. 3, 1980, pp. 353-381. doi:10.1007/BF00935493

[17] 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

[18] J. G. Ecker and J. H. Song, “Optimizing a Linear Function over an Efficient Set,” Journal of Optimization Theory and Applications, Vol. 83, No. 3, 1994, pp. 541-563. doi:10.1007/BF02207641