Telecommunications network design and max-min optimization problem

• Autorzy: Ogryczak W. , Pióro M. , Tomaszewski A.
• Języki publikacji: EN

Abstrakty

EN

Telecommunications networks are facing increasing demand for Internet services. Therefore, the problem of telecommunications network design with the objective to maximize service data flows and provide fair treatment of all services is very up-to-date. In this application, the so-called max-min fair (MMF) solution concept is widely used to formulate the resource allocation scheme. It assumes that the worst service performance is maximized and the solution is additionally regularized with the lexicographic maximization of the second worst performance, the third one, etc. In this paper we discuss solution algorithms for MMF problems related to telecommunications network design. Due to lexicographic maximization of ordered quantities, the MMF solution concept cannot be tackled by the standard optimization model (mathematical programme). However, one can formulate a sequential lexicographic optimization procedure. The basic procedure is applicable only for convex models, thus it allows to deal with basic design problems but fails if practical discrete restrictions commonly arriving in telecommunications network design are to be taken into account. Then, however, alternative sequential approaches allowing to solve non-convex MMF problems can be used.

Słowa kluczowe

EN

network design; resource allocation; fairness; lexicographic optimization; lexicographic max-min

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2005
• Tom: nr 3
• Strony: 43--56
• Opis fizyczny: Bibliogr. 38 poz.

Twórcy

autor

Ogryczak W.

• Institute of Control & Computation Engineering, Warsaw University of Technology, Nowowiejska st 15/19, 00-665 Warsaw, Poland

autor

Pióro M.

• Institute of Telecommunications Warsaw University of Technology Nowowiejska st 15/19 00-665 Warsaw, Poland

autor

Tomaszewski A.

• Institute of Telecommunications Warsaw University of Technology Nowowiejska st 15/19 00-665 Warsaw, Poland

Bibliografia

• [1] F. A. Behringer, “A simplex based algorithm for the lexicographically extended linear maxmin problem”, Eur. J. Oper. Res., vol. 7, pp. 274–283, 1981.
• [2] F. A. Behringer, “Linear multiobjective maxmin optimization and some Pareto and lexmaxmin extensions”, OR Spektrum, vol. 8, pp. 25–32, 1986.
• [3] D. Bertsekas and R. Gallager, Data Networks. Englewood Cliffs: Prentice-Hall, 1987.
• [4] R. E. Burkard and F. Rendl, “Lexicographic bottleneck problems”, Oper. Res. Lett., vol. 10, pp. 303–308, 1991.
• [5] F. Della Croce, V. T. Paschos, and A. Tsoukias, “An improved general procedure for lexicographic bottleneck problem”, Oper. Res. Lett., vol. 24, pp. 187–194, 1999.
• [6] R. Denda, A. Banchs, and W. Effelsberg, “The fairness challenge in computer networks”, LNCS, vol. 1922, pp. 208–220, 2000.
• [7] M. Dresher, Games of Strategy. Englewood Cliffs: Prentice-Hall, 1961.
• [8] D. Dubois, Ph. Fortemps, M. Pirlot, and H. Prade, “Leximin optimality and fuzzy set-theoretic operations”, Eur. J. Oper. Res., vol. 130, pp. 20–28, 2001.
• [9] M. Ehrgott, “Discrete decision problems, multiple criteria optimization classes and lexicographic max-ordering”, in Trends in Multicriteria Decision Making, T. J. Stewart and R. C. van den Honert, Eds. Berlin: Springer, 1998, pp. 31–44.
• [10] H. Isermann, “Linear lexicographic optimization”, OR Spektrum, vol. 4, pp. 223–228, 1982.
• [11] J. Jaffe, “Bottleneck flow control”, IEEE Trans. Commun., vol. 7, pp. 207–237, 1980.
• [12] R. S. Klein, H. Luss, and D. R. Smith, “A lexicographic minimax algorithm for multiperiod resource allocation”, Math. Programm., vol. 55, pp. 213–234, 1992.
• [13] J. Kleinberg, Y. Rabani, and E. Tardos, “Fairness in routing and load balancing”, in Proc. 40th Ann. IEEE Symp. Found. Comput. Sci., New York, USA, 1999.
• [14] M. M. Kostreva and W. Ogryczak, “Linear optimization with multiple equitable criteria”, RAIRO Oper. Res., vol. 33, pp. 275–297, 1999.
• [15] J. K. Krarup and P. M. Pruzan, “Reducibility of minimax to minisum 0–1 programming problems”, Eur. J. Oper. Res., vol. 5, pp. 125–132, 1981.
• [16] H. Luss, “On equitable resource allocation problems: a lexicographic minimax approach”, Oper. Res., vol. 47, pp. 361–378, 1999.
• [17] E. Marchi and J. A. Oviedo, “Lexicographic optimality in the multiple objective linear programming: the nucleolar solution”, Eur. J. Oper. Res., vol. 57, pp. 355–359, 1992.
• [18] A. W. Marshall and I. Olkin, Inequalities: Theory of Majorization and Its Applications. New York: Academic Press, 1979.
• [19] P. Nilsson and M. Pióro, Solving Dimensioning Problems for Proportionally Fair Networks Carrying Elastic Traffic. Lund: Lund Institute of Technology, 2002.
• [20] P. Nilsson, M. Pióro, and Z. Dziong, “Link protection within an existing backbone network”, in Proc. Int. Netw. Opt. Conf. INOC, Paris-Evry, France, 2003.
• [21] W. Ogryczak, “On the lexicographic minimax approach to location problems”, Eur. J. Oper. Res., vol. 100, pp. 566–585, 1997.
• [22] W. Ogryczak, Wielokryterialna optymalizacja liniowa i dyskretna. Modele preferencji i zastosowania do wspomagania decyzji. Warszawa: Wydawnictwa Uniwersytetu Warszawskiego, 1997 (in Polish).
• [23] W. Ogryczak, “Comments on properties of the minimax solutions in goal programming”, Eur. J. Oper. Res., vol. 132, pp. 17–21, 2001.
• [24] W. Ogryczak and T. Śliwiński, “On equitable approaches to resource allocation problems: the conditional minimax solution”, J. Telecommun. Inform. Technol., no. 3, pp. 40–48, 2002.
• [25] W. Ogryczak and T. Śliwiński, “On solving linear programs with the ordered weighted averaging objective”, Eur. J. Oper. Res., vol. 148, pp. 80–91, 2002.
• [26] W. Ogryczak and A. Tamir, “Minimizing the sum of the k largest functions in linear time”, Inform. Proc. Lett., vol. 85, pp. 117–122, 2003.
• [27] M. Pióro and D. Medhi, Routing, Flow and Capacity Design in Communication and Computer Networks. San Francisco: Morgan Kaufmann, 2004.
• [28] M. Pióro, P. Nilsson, E. Kubilinskas, and G. Fodor, “On efficient max-min fair routing algorithms”, in Proc. 8th IEEE Int. Symp. Comput. Commun. ISCC’03, Antalya, Turkey, 2003.
• [29] J. A. M. Potters and S. H. Tijs, “The nucleolus of a matrix game and other nucleoli”, Math. Oper. Res., vol. 17, pp. 164–174, 1992.
• [30] J. Rawls, The Theory of Justice. Cambridge: Harvard University Press, 1971.
• [31] J. R. Rice, “Tschebyscheff approximation in a compact metric space”, Bull. Amer. Math. Soc., vol. 68, pp. 405–410, 1962.
• [32] D. Schmeidler, “The nucleolus of a characteristic function game”, SIAM J. Appl. Math., vol. 17, pp. 1163–1170, 1969.
• [33] R. E. Steuer, Multiple Criteria Optimization: Theory, Computation & Applications. New York: Wiley, 1986.
• [34] A. Tomaszewski, “A polynomial algorithm for solving a general maxmin fairness problem”, in Proc. 2nd Polish-German Teletraffic Symp. PGTS 2002, Gdańsk, Poland, 2002, pp. 253–258.
• [35] A. P. Wierzbicki, M. Makowski, and J. Wessels, Eds., Model Based Decision Support Methodology with Environmental Applications. Dordrecht: Kluwer, 2000.
• [36] R. R. Yager, “On ordered weighted averaging aggregation operators in multicriteria decision making”, IEEE Trans. Syst., Man Cyber., vol. 18, pp. 183–190, 1988.
• [37] R. R. Yager, “Constrained OWA aggregation”, Fuzzy Sets Syst., vol. 81, pp. 89–101, 1996.
• [38] R. R. Yager, “On the analytic representation of the Leximin ordering and its application to flexible constraint propagation”, Eur. J. Oper. Res., vol. 102, pp. 176–192, 1997.