On the Lexicographic Centre of Multiple Objective Optimization

详细信息    查看全文

• 作者：Zhang Jiangao ; Shitao Yang
• 关键词：Multiple objective programming ; Lexicographic order ; Lexicographic centre ; Efficient solution ; Image set ; $$\theta $$ θ ; image set ; 49M29 ; 65K05 ; 90C05 ; 90C29 ; 90C47
• 刊名：Journal of Optimization Theory and Applications
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：168
• 期：2
• 页码：600-614
• 全文大小：468 KB
• 参考文献：1.Ogryczak, W.: On the lexicographic minimax approach to location problems. Eur. J. Oper. Res. 100, 566–585 (1997)CrossRef MATH
  2.Luss, H.: On equitable resource allocation problems: a lexicographic minimax approach. Oper. Res. 47(3), 182–187 (1999)CrossRef
  3.Shmeidler, D.: The nucleolus of a characteristic function game. SIAM J. Appl. Math. 17, 1163–1170 (1969)CrossRef MathSciNet
  4.Maschler, M., Peleg, B., Shapley, L.S.: Geometric properties of the kernel, nucleolus and related solution concepts. Math. Oper. Res. 4, 303–338 (1979)CrossRef MathSciNet MATH
  5.Dragan, I.: A procedure for finding the nucleolus of a cooperative n person game. Zeitschrift für Oper. Res. 25(5), 119–131 (1981)MathSciNet MATH
  6.Benoît, J.-P.: The nucleolus is contested-garment-consistent: a direct proof. J. Econ. Theory 77, 192–196 (1997)CrossRef MATH
  7.Potters, Jos A.M., Reijnierse, J.H., Ansing, M.: Computing the nucleolus by solving a prolonged simplex algorithm. Math. Oper. Res 21, 757–768 (1996)CrossRef MathSciNet MATH
  8.Meertens, M., Potters, Jos A.M.: The nucleolus of trees with revenues. Math. Method Oper. Res. 64(2), 363–382 (2006)CrossRef MathSciNet MATH
  9.Potters, Jos A.M., Reijnierse, H., Biswas, A.: The nucleolus of balanced simple flow networks. Game Econ. Behav. 54(1), 205–225 (2006)CrossRef MathSciNet MATH
  10.Maschler, M., Potters, Jos A.M., Reijnierse, H.: The nucleolus of a standard tree game revisited: a study of its monotonicity and computational properties. Int. J. Game Theory 39(1–2), 89–104 (2010)CrossRef MathSciNet MATH
  11.Marchi, E., Oviedo, J.A.: Lexicographic optimality in the multiple objective linear programming: the nucleolar solution. Eur. J. Oper. Res. 57(3), 355–359 (1992)CrossRef MATH
  12.Kostreva, M.M., Ogryczak, W., Wierzbicki, A.: Equitable aggregations and multiple criteria analysis. Eur. J. Oper. Res. 158, 362–377 (2004)CrossRef MathSciNet MATH
  13.Ogryczak, W., Sliwinski, T., Wierzbicki, A.: Fair resource allocation schemes and network dimensioning problems. J. Telecommun. Inf. Technol. 3, 34–42 (2003)
  14.Ogryczak, W., Śliwiński, T.: On direct methods for lexicographic min–max optimization. Lect. Notes Comput. Sci. 3982, 802–811 (2006)CrossRef
  15.Radunović, B., Le Boudec, J.-Y.: A unified framework for max–min and min–max fairness with applications. IEEE/ACM Trans. Netw. 15(5), 1073–1083 (2007)CrossRef
  16.Klein, R.S., Luss, H., Smith, D.R.: A lexicographic minimax algorithm for multiperiod resource allocation. Math. Program. 55, 213–234 (1992)CrossRef MathSciNet MATH
  17.Tomaszewski, A.: A polynomial algorithm for solving a general max–min fairness problem. Eur. Trans. Telecommun. 16, 233–240 (2005)CrossRef
  18.Ogryczak, W., Pióro, M., Tomaszewski, A.: Telecommunications network design and max–min optimization problem. J. Telecommun. Inf. Technol. 3, 43–56 (2005)
  19.Ehrgott, M., Holder, A., Reese, J.: Beam selection in radiotherapy design. Linear Algebra Appl. 428, 1272–1312 (2008)CrossRef MathSciNet MATH
  20.Pióro, M.: Fair routing and related optimization problems. In: Proceedings of the 15th International Conference on Advanced Computing and Communications, Guwahati, Assam, pp. 229–235. IEEE Computer Society (2007)
  21.Pióro, M., Nilsson, P., Kubilinskas, E., Fodor, G.: On efficient max-min fair routing algorithms. In: Proceedings of the Eighth IEEE International Symposium on Computers and Communication (ISCC’03), Kemer - Antalya, Turkey, pp. 365–372 vol. 1 (2003)
  22.Sun, M.: Some issues in measuring and reporting solution quality of interactive multiple objective programming procedures. Eur. J. Oper. Res. 162, 468–483 (2005)CrossRef MATH
  23.Ogryczak, W., Wierzbicki, A.: On multi-criteria approaches to bandwidth allocation. Control Cybern. 33(3), 427–448 (2004)MathSciNet MATH
  24.Ogryczak, W., Wierzbicki, A., Milewskia, M.: A multi-criteria approach to fair and efficient bandwidth allocation. Omega 36, 451–463 (2008)CrossRef
  25.Hoang, D.T., Vitter, J.S.: Efficient Algorithms for MPEG Video Compression. Wiley, New York, NY (2001)
  26.Dragan, I.: A game theoretic approach for solving the multiobjective linear programming problems. Lib. Math. 30, 149–158 (2010)MathSciNet MATH
  27.Behringer, F.A.: A simplex based algorithm for the lexicographically extended linear maxmin problem. Eur. J. Oper. Res. 7, 274–283 (1981)CrossRef MathSciNet MATH
  28.Pourkarimi, L., Zarepisheh, M.: A dual-based algorithm for solving lexicographic multiple objective programs. Eur. J. Oper. Res. 176, 1348–1356 (2007)CrossRef MathSciNet MATH
  29.Klee, V., Minty, G.J.: How Good is the Simplex Algorithm? Inequalities-III. Academic Press, New York (1972)
  30.Friedmann, O., Hansen, T., Zwick, U.: Subexponential lower bounds for randomized pivoting rules for the simplex algorithm. In: STOC’11 Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pp. 283–292. ACM, San Jose, California, New York (2011)
  31.Behringer, F.A.: Linear multiobjective maxmin optimization and some Pareto and lexmaxmin extensions. OR Spektrum 8, 25–32 (1986)CrossRef MathSciNet MATH
  32.Khorram, E., Zarepisheh, M., Ghaznavi-ghosoni, B.A.: Sensitivity analysis on the priority of the objective functions in lexicographic multiple objective linear programs. Eur. J. Oper. Res. 207, 1162–1168 (2010)CrossRef MathSciNet MATH
  33.Luenberger, D.G., Ye, Y.: Linear and Nonlinear Programming, 3rd edn. Springer, New York, NY (2010)
  
• 作者单位：Zhang Jiangao (1) (2)
  Shitao Yang (3)
  
  1. Faculty of Construction Management and Real Estate, Chongqing University, Chongqing, 400045, China
  2. State Key Laboratory of Hydraulics and Mountain River Engineering, Sichuan University, Chengdu, China
  3. The Nathan M. Bisk College of Business, Florida Institute of Technology, 150 W. University Blvd, Melbourne, FL, 32901, USA
  
• 刊物主题：Calculus of Variations and Optimal Control; Optimization; Optimization; Theory of Computation; Applications of Mathematics; Engineering, general; Operations Research/Decision Theory;
• 出版者：Springer US
• ISSN：1573-2878

文摘

We study the lexicographic centre of multiple objective optimization. Analysing the lexicographic-order properties yields the result that, if the multiple objective programming’s lexicographic centre is not empty, then it is a subset of all efficient solutions. It exists if the image set of multiple objective programming is bounded below and closed. The multiple objective linear programming’s lexicographic centre is nonempty if and only if there exists an efficient solution to the multiple objective linear programming. We propose a polynomial-time algorithm to determine whether there is an efficient solution to multiple objective linear programming, and we solve the multiple objective linear programming’s lexicographic centre by calculating at most the same number of dual linear programs as the number of objective functions and a system of linear inequalities. Keywords Multiple objective programming Lexicographic order Lexicographic centre Efficient solution Image set \(\theta \)-image set