Generating Efficient Solutions in Bilevel Multi-Objective Programming Problems

Calice Olivier Pieume, Patrice Marcotte, Laure Pauline Fotso, Patrick Siarry

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.
Department of Mathematics, 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.

DOI: 10.4236/ajor.2013.32026                

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.

Keywords

Multi-Objective Programming; Bilevel Programming; Efficient Solution; Efficient Edge; Hierarchical Systems

Conflicts of Interest

The authors declare no conflicts of interest.

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