Telecommunications network design and max-min optimization problem
DOI:
https://doi.org/10.26636/jtit.2005.3.326Keywords:
network design, resource allocation, fairness, lexicographic optimization, lexicographic max-min.Abstract
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 maxmin 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, theMMF 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.
Downloads
References
[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.
View in Google Scholar
[2] F. A. Behringer, „Linear multiobjective maxmin optimization and some Pareto and lexmaxmin extensions”, OR Spektrum, vol. 8, pp. 25-32, 1986.
View in Google Scholar
[3] D. Bertsekas and R. Gallager, Data Networks. Englewood Cliffs: Prentice-Hall, 1987.
View in Google Scholar
[4] R. E. Burkard and F. Rendl, „Lexicographic bottleneck problems”, Oper. Res. Lett., vol. 10, pp. 303-308, 1991.
View in Google Scholar
[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.
View in Google Scholar
[6] R. Denda, A. Banchs, and W. Effelsberg, „The fairness challenge in computer networks”, LNCS, vol. 1922, pp. 208-220, 2000.
View in Google Scholar
[7] M. Dresher, Games of Strategy. Englewood Cliffs: Prentice-Hall, 1961.
View in Google Scholar
[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.
View in Google Scholar
[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.
View in Google Scholar
[10] H. Isermann, „Linear lexicographic optimization”, OR Spektrum, vol. 4, pp. 223-228, 1982.
View in Google Scholar
[11] J. Jaffe, „Bottleneck flow control”, IEEE Trans. Commun., vol. 28, pp. 207-237, 1980.
View in Google Scholar
[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.
View in Google Scholar
[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.
View in Google Scholar
[14] M. M. Kostreva and W. Ogryczak, „Linear optimization with multiple equitable criteria”, RAIRO Oper. Res., vol. 33, pp. 275-297, 1999.
View in Google Scholar
[15] J. K. Krarup and P. M. Pruzan, „Reducibility of minimax to minimum 0-1 programming problems”, Eur. J. Oper. Res., vol. 5, pp. 125-132, 1981.
View in Google Scholar
[16] H. Luss, „On equitable resource allocation problems: a lexicographic minimax approach”, Oper. Res., vol. 47, pp. 361-378, 1999.
View in Google Scholar
[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.
View in Google Scholar
[18] A. W. Marshall and I. Olkin, Inequalities: Theory of Majorization and Its Applications. New York: Academic Press, 1979.
View in Google Scholar
[19] P. Nilsson and M. Pióro, Solving Dimensioning Problems for Proportionally Fair Networks Carrying Elastic Traffic. Lund: Lund Institute of Technology, 2002.
View in Google Scholar
[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.
View in Google Scholar
[21] W. Ogryczak, „On the lexicographic minimax approach to location problems”, Eur. J. Oper. Res., vol. 100, pp. 566-585, 1997.
View in Google Scholar
[22] W. Ogryczak, Wielokryterialna optymalizacja liniowa i dyskretna. Modele preferencji i zastosowania do wspomagania decyzji. Warszawa: Wydawnictwa Uniwersytetu Warszawskiego, 1997 (in Polish).
View in Google Scholar
[23] W. Ogryczak, „Comments on properties of the minimax solutions in goal programming”, Eur. J. Oper. Res., vol. 132, pp. 17-21, 2001.
View in Google Scholar
[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.
View in Google Scholar
[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.
View in Google Scholar
[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.
View in Google Scholar
[27] M. Pióro and D. Medhi, Routing, Flow and Capacity Design in Communication and Computer Networks. San Francisco: Morgan Kaufmann, 2004.
View in Google Scholar
[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.
View in Google Scholar
[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.
View in Google Scholar
[30] J. Rawls, The Theory of Justice. Cambridge: Harvard University Press, 1971.
View in Google Scholar
[31] J. R. Rice, „Tschebyscheff approximation in a compact metric space”, Bull. Amer. Math. Soc., vol. 68, pp. 405-410, 1962.
View in Google Scholar
[32] D. Schmeidler, „The nucleolus of a characteristic function game”, SIAM J. Appl. Math., vol. 17, pp. 1163-1170, 1969.
View in Google Scholar
[33] R. E. Steuer, Multiple Criteria Optimization: Theory, Computation & Applications. New York: Wiley, 1986.
View in Google Scholar
[34] A. Tomaszewski, „A polynomial algorithm for solving a general max-min fairness problem”, in Proc. 2nd Polish-German Teletraffic Symp. PGTS 2002, Gdańsk, Poland, 2002, pp. 253-258.
View in Google Scholar
[35] A. P. Wierzbicki, M. Makowski, and J. Wessels, Eds., Model Based Decision Support Methodology with Environmental Applications. Dordrecht: Kluwer, 2000.
View in Google Scholar
[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.
View in Google Scholar
[37] R. R. Yager, „Constrained OWA aggregation”, Fuzzy Sets Syst., vol. 81, pp. 89-101, 1996.
View in Google Scholar
[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.
View in Google Scholar
Downloads
Submitted
Published
Issue
Section
License
Copyright (c) 2005 Journal of Telecommunications and Information Technology
This work is licensed under a Creative Commons Attribution 4.0 International License.
