Efficient Approximation Methods for Lexicographic Max-Min Optimization

• Autorzy: Śliwiński Tomasz

Identyfikatory

DOI

10.26636/jtit.2024.1.1421

• Języki publikacji: EN

Abstrakty

EN

Lexicographic max-min (LMM) optimization is of considerable importance in many fairness-oriented applications. LMM problems can be reformulated in a way that allows to solve them by applying the standard lexicographic maximization algorithm. However, the reformulation introduces a large number of auxiliary variables and linear constraints, making the process computationally complex. In this paper, two approximation schemes for such a reformulation are presented, resulting in problem size reduction and significant performance gains. Their influence on the quality of the solution is shown in a series of computational experiments concerned with the fair network dimensioning and bandwidth allocation problem.

Słowa kluczowe

EN

fairness; lexicographic max-min; lexicographic optimization; network dimensioning

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2024
• Tom: nr 1
• Strony: 46--53
• Opis fizyczny: Bibliogr. 20 poz., tab.

Twórcy

autor

Śliwiński Tomasz

• Institute of Control and Computation Engineering Warsaw University of Technology, Warsaw, Poland

• https://orcid.org/0000-0002-5111-1830

Bibliografia

• [1] H. Luss, Equitable Resource Allocation: Models, Algorithms, and Applications, Hoboken: John Wiley & Sons, 376 p., 2012.
• [2] W. Ogryczak, Linear and Discrete Optimization with Multiple Criteria: Preference Models and Applications to Decision Support, Warsaw University Press, 1997 (ISBN: 9788323099413) [in Polish].
• [3] W. Ogryczak, M. Pióro, and A. Tomaszewski, "Telecommunication Network Design and Max-min Optimization Problem", Journal of Telecommunication and Information Technology, no. 3, pp. 43-56, 2005 (https://jtit.pl/jtit/article/view/326).
• [4] W. Ogryczak, "On the Lexicographic Minimax Approach to Location Problems", European Journal of Operational Research, vol. 100, no. 3, pp. 566-585, 1997.
• [5] V.X. Chen and J.N. Hooker, "A Guide to Formulating Fairness in an Optimization Model", Annals of Operations Research, vol. 326, no. 1, pp. 581-619, 2023.
• [6] J. Kleinberg, Y. Rabani, and E. Tardos, "Fairness in Routing and Load Balancing", Journal of Computer and System Sciences, vol. 63, no. 1, pp. 2-21, 2001.
• [7] M. Pióro and D. Medhi, Routing, Flow, and Capacity Design in Communication and Computer Networks, San Francisco: Morgan Kaufman, 800 p., 2004.
• [8] J. Jaffe, "Bottleneck Flow Control", IEEE Transactions on Communications, vol. 29, no. 7, pp. 954-962, 1981.
• [9] D. Nace, L.N. Doan, O. Klopfenstein, and A. Bashllari, "Max-min Fairness in Multi-commodity Flows", Computers and Operations Research, vol. 35, no. 2, pp. 557-573, 2008.
• [10] M. Pióro, M. Dzida, E. Kubilinskas, and P. Nilsson, "Applications of the Max-min Fairness Principle in Telecommunication Network Design", in: Next Generation Internet Networks, 2005, Rome, Italy, pp. 219-225, 2005.
• [11] W. Ogryczak, "Location Problems from the Multiple Criteria Perspective: Efficient Solutions", Archives of Control Sciences, vol. 7, no. 3, pp. 161-180, 1998 (https://www.ia.pw.edu.pl/ wogrycza/publikacje/artykuly/mcdmlocn.pdf).
• [12] F.A. Behringer, "A Simplex Based Algorithm for the Lexicographically Extended Linear Maxmin Problem", European Journal of Operational Research, vol. 7, no. 3, pp. 274-283, 1981.
• [13] R.S. Klein, H. Luss, and U.G. Rothblum, "Minimax Resource Allocation Problems with Resource-substitutions Represented by Graphs", Operations Research, vol. 41, no. 5, pp. 959-971, 1993.
• [14] W. Ogryczak and T. Śliwiński, "On Equitable Approaches to Resource Allocation Problems: The Conditional Minimax Solution", Journal of Telecommunications and Information Technology, no. 3, pp. 40-48, 2002 (https://jtit.pl/jtit/article/view/134).
• [15] W. Ogryczak and A. Tamir, "Minimizing the Sum of the k Largest Functions in Linear Time", Information Processing Letters, vol. 85, no. 3, pp. 117-122, 2003.
• [16] W. Ogryczak and T. Śliwiński, "On Direct Methods for Lexicographic Min-Max Optimization", Lecture Notes in Computer Science, vol. 3982, pp. 802-811, 2006.
• [17] R.R. Yager, "On the Analytic Representation of the Leximin Ordering and Its Application to Flexible Constraint Propagation", European Journal of Operational Research, vol. 102, no. 1, pp. 176-192, 1997.
• [18] W. Ogryczak and T. Śliwiński, "Sequential Algorithms for Exact and Approximate Max-min Fair Bandwidth Allocation", in: 2012 15th International Telecommunications Network Strategy and Planning Symposium (NETWORKS), Rome, Italy, 2012.
• [19] W. Ogryczak and T. Śliwiński, "Sequential Algorithms for Max-min Fair Bandwidth Allocation", in: Proceedings of the European Computing Conference, vol. 1, pp. 511-522, 2009.
• [20] O. Orlowski, M. Pióro, A. Tomaszewski, and R. Wessäly, "SNDlib 1.0-Survivable Network Design Library", Network, vol. 55, no. 3, pp. 276-286, 2010.