SZACOWANIE KOSZTU SPRAWIEDLIWOŚCI ALOKACJI OBCIĄŻEŃ W SIECI DLA METODY OPTYMALIZACJI UPORZĄDKOWANEJ ŚREDNIEJ WAŻONEJ

• Authors: Zalewski Grzegorz , Ogryczak Włodzimierz

Title variants

EN

ESTIMATION THE PRICE OF FAIRNESS FOR NETWORK BANDWIDTH ALLOCATION BY THE OWA OPTIMIZATION

• Languages of publication: PL

Abstracts

PL

Jednym z wielu problemów podczas wymiarowania sieci telekomunikacyjnych jest optymalizacja przepływów zapotrzebowań między zadanymi węzłami. Jednym ze sposobów wykorzystywanych do tego celu jest formułowanie zadania programowania liniowego. W niniejszej pracy skupiono się na optymalizacji ulokowania przepływów na danych ścieżkach w grafie nieskierowanym. Dodatkowo ważnym elementem zadania jest fakt, że ścieżki dzielą między sobą ograniczone zasoby przepustowości, co sprawia zaistnienie rzeczywistego problemu decyzyjnego. Dla tak sformułowanego problemu wykorzystano formułę krawędź-ścieżka programowania liniowego oraz implementację zadania w standardzie AMPL. W pracy oszacowano koszt rozwiązania sprawiedliwego dla modelu OWA (Ordered Weighted Averaging) w porównaniu do rozwiązania maksymalizującego przepływy na ścieżkach oraz do rozwiązania modelu MMF (maximin fairness). Efektem końcowym pracy jest przedstawienie wyników oraz podsumowanie analizy otrzymanych rozwiązań na bazie danych przykładowych, stanowiących odniesienie do sieci telekomunikacyjnej szkieletowej Polski, gdzie głównym miernikiem jest różnica wartości funkcji celu dla wymienionych metod sprawiedliwej optymalizacji oraz rozwiązania maksymalizującego przepływ całkowity.

EN

An important problem when designing a telecommunication network is to optimize the flow demands at the network between pre-defined nodes. One of the solutions used for this purpose is to formulate the linear programming. In this paper we focus on the optimization of locating the data flow path in an undirected network. It provides an actual decision-making problem. For such a problem the link-path formula has been chosen. Problem also has brought to linear programming and implemented in AMPL standard. The study estimated the price of fairness for the considered model OWA (Ordered Weighted Averaging) compared to solve maximizing flows on the paths and to solve the model MMF (Maximin fairness). The final effect of the work is to present the results and a summary of the analysis, obtained solutions based on sample data by reference to the telecommunication network which in this case was the backbone Polish net. The main measure is the difference between the value of the objective function for these fair methods and solutions maximizing total flow.

Keywords

PL

etoda optymalizacji średniej ważonej; OWA; optymalizacja sprawiedliwa; optymalizacja wielokryterialna; optymalizacja sieci; koszt sprawiedliwości; problemy decyzyjne; programowanie liniowe; algorytmy

EN

optimization; ordered weighted averaging; OWA; fair optimization; multi-criteria optimization; network optimization; the price of fairness; decision-making problems; linear programming; algorithms

• Publisher: Katedra Ekonometrii i Statystyki, Szkoła Główna Gospodarstwa Wiejskiego w Warszawie
• Journal: Metody Ilościowe w Badaniach Ekonomicznych
• Year: 2015
• Volume: 16
• Issue: 4
• Pages: 230-241

Dates

published

2015

Contributors

author

Zalewski Grzegorz

• Instytut Łączności – Państwowy Instytut Badawczy

author

Ogryczak Włodzimierz

• Instytut Automatyki i Informatyki Stosowanej, Politechnika Warszawska

References

• Bertsimas D., Farias Vivek F., Trichakis N. (2011) The Price of Fairness, Operations Research, Vol. 59, No. 1, pp. 17-31.
• Liu X. (2006) Some Properties of the Weighted OWA Operator, IEEE Trans. Syst. Man Cyber. B, Vol. 368, pp. 118–127.
• Luss H. (1999) On Equitable Resource Allocation Problems: A Lexicographic Minimax Approach, Operation Research, Vol. 47, No. 3, pp. 361-378.
• Ogryczak W. (1997) Wielokryterialna Optymalizacja Liniowa i Dyskretna, modele preferencji i zastosowania do wspomagania decyzji, Wydawnictwa Uniwersytetu Warszawskiego, Warszawa.
• Ogryczak W. (2014) Fair Optimization – Methodological Foundations of Fairness in Network Resource Allocation, IEEE 38th Annual International Computers, Software and Applications Conference Workshops.
• Ogryczak W. (2014) Tail mean and related robust solution concepts, International Journal of Systems Science: Principles and Applications of Systems and Integration, Vol. 45, No. 1, pp. 29–38.
• Ogryczak W. and Śliwiński T. (2003) On solving linear programs with the ordered weighted averaging objective, European Journal of Operational Research, Vol. 148, No. 1, pp. 80–91.
• Ogryczak W. and Tamir A. (2003) Minimizing the sum of the 𝑘 largest functions in linear time, Information Processing Letters, Vol. 85, No. 3, pp. 117–122.
• Ogryczak W., Luss H., Pióro M., Nace D., Tomaszewski A. (2014) Fair Optimization and Networks: A Survey, Journal of Applied Mathematics, Vol. 2014, pp. 1-25.
• Yager R. R. (1988) On ordered weighted averaging aggregation operators in multicriteria decision making, IEEE Transactions on Systems, Man, and Cybernetics, Vol. 18, No. 1, pp. 183–190.
• Yager R. R. (1996) Constrained OWA aggregation, Fuzzy Sets and Systems, Vol. 81, No. 1, pp. 89–101.
• Yager R. R., Kacprzyk J. and Beliakov G. (2011) Recent Developments in the Ordered Weighted Averaging Operators: Theory and Practice, Springer.