Efficient Approximation Methods for Lexicographic Max-Min Optimization
DOI:
https://doi.org/10.26636/jtit.2024.1.1421Keywords:
fairness, lexicographic max-min, lexicographic optimization, network dimensioningAbstract
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.
Downloads
References
H. Luss, Equitable Resource Allocation: Models, Algorithms, and Applications, Hoboken: John Wiley & Sons, 376 p., 2012.
View in Google Scholar
W. Ogryczak, Linear and Discrete Optimization with Multiple Criteria: Preference Models and Applications to Decision Support, Warsaw University Press, 1997 (ISBN: 9788323099413) [in Polish].
View in Google Scholar
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).
View in Google Scholar
W. Ogryczak, "On the Lexicographic Minimax Approach to Location Problems", European Journal of Operational Research, vol. 100, no. 3, pp. 566-585, 1997.
View in Google Scholar
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.
View in Google Scholar
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.
View in Google Scholar
M. Pióro and D. Medhi, Routing, Flow, and Capacity Design in Communication and Computer Networks, San Francisco: Morgan Kaufman, 800 p., 2004.
View in Google Scholar
J. Jaffe, "Bottleneck Flow Control", IEEE Transactions on Communications, vol. 29, no. 7, pp. 954-962, 1981.
View in Google Scholar
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.
View in Google Scholar
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.
View in Google Scholar
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).
View in Google Scholar
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.
View in Google Scholar
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.
View in Google Scholar
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).
View in Google Scholar
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.
View in Google Scholar
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.
View in Google Scholar
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.
View in Google Scholar
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.
View in Google Scholar
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.
View in Google Scholar
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.
View in Google Scholar
Downloads
Published
Issue
Section
License
Copyright (c) 2024 Tomasz Śliwiński
This work is licensed under a Creative Commons Attribution 4.0 International License.