Abstract
The approach called the Lexicographic Min-Max (LMM) optimization depends on searching for solutions minimal according to the lex-max order on a multidimensional outcome space. LMM is a refinement of the standard Min-Max optimization, but in the former, in addition to the largest outcome, we minimize also the second largest outcome (provided that the largest one remains as small as possible), minimize the third largest (provided that the two largest remain as small as possible), and so on. The necessity of point-wise ordering of outcomes within the lexicographic optimization scheme causes that the LMM problem is hard to implement. For convex problems it is possible to use iterative algorithms solving a sequence of properly defined Min-Max problems by eliminating some blocked outcomes. In general, it may not exist any blocked outcome thus disabling possibility of iterative Min-Max processing. In this paper we analyze two alternative optimization models allowing to form lexicographic sequential procedures for various nonconvex (possibly discrete) LMM problems. Both the approaches are based on sequential optimization of directly defined artificial criteria. The criteria can be introduced into the original model with some auxiliary variables and linear inequalities thus the methods are easily implementable.
The research was supported by the Ministry of Science and Information Society Technologies under grant 3T11C 005 27 “Models and Algorithms for Efficient and Fair Resource Allocation in Complex Systems.”
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Behringer, F.A.: A simplex based algorithm for the lexicographically extended linear maxmin problem. Eur. J. Opnl. Res. 7, 274–283 (1981)
Bertsekas, D., Gallager, R.: Data Networks. Prentice-Hall, Englewood Cliffs (1987)
Burkard, R.E., Rendl, F.: Lexicographic bottleneck problems. Oper. Res. Let. 10, 303–308 (1991)
Della Croce, F., Paschos, V.T., Tsoukias, A.: An improved general procedure for lexicographic bottleneck problem. Oper. Res. Let. 24, 187–194 (1999)
Denda, R., Banchs, A., Effelsberg, W.: The fairness challenge in computer networks. In: Crowcroft, J., Roberts, J., Smirnov, M.I. (eds.) QofIS 2000. LNCS, vol. 1922, pp. 208–220. Springer, Heidelberg (2000)
Dresher, M.: Games of Strategy. Prentice-Hall, Englewood Cliffs (1961)
Dubois, D., Fortemps, P., Pirlot, M., Prade, H.: Leximin optimality and fuzzy set-theoretic operations. Eur. J. Opnl. Res. 130, 20–28 (2001)
Ehrgott, M.: Discrete decision problems, multiple criteria optimization classes and lexicographic max-ordering. In: Stewart, T.J., van den Honert, R.C. (eds.) Trends in Multicriteria Decision Making, pp. 31–44. Springer, Berlin (1998)
Klein, R.S., Luss, H., Smith, D.R.: A lexicographic minimax algorithm for multiperiod resource allocation. Math. Progr. 55, 213–234 (1992)
Kostreva, M.M., Ogryczak, W.: Linear optimization with multiple equitable criteria. RAIRO Oper. Res. 33, 275–297 (1999)
Luss, H.: On equitable resource allocation problems: A lexicographic minimax approach. Oper. Res. 47, 361–378 (1999)
Marchi, E., Oviedo, J.A.: Lexicographic optimality in the multiple objective linear programming: the nucleolar solution. Eur. J. Opnl. Res. 57, 355–359 (1992)
Ogryczak, W.: Linear and Discrete Optimization with Multiple Criteria: Preference Models and Applications to Decision Support (in Polish). Warsaw Univ. Press, Warsaw (1997)
Ogryczak, W.: On the lexicographic minimax approach to location problems. Eur. J. Opnl. Res. 100, 566–585 (1997)
Ogryczak, W.: Multiple criteria optimization and decisions under risk. Control & Cyber 31, 975–1003 (2002)
Ogryczak, W., Pióro, M., Tomaszewski, A.: Telecommunication network design and max-min optimization problem. J. Telecom. Info. Tech. 3/05, 43–56 (2005)
Ogryczak, W., Śliwiński, T.: On equitable approaches to resource allocation problems: the conditional minimax solution, J. Telecom. Info. Tech. 3/02, 40–48 (2002)
Ogryczak, W., Śliwiński, T.: On solving linear programs with the ordered weighted averaging objective. Eur. J. Opnl. Res. 148, 80–91 (2003)
Ogryczak, W., Tamir, A.: Minimizing the sum of the k largest functions in linear time. Inform. Proc. Let. 85, 117–122 (2003)
Pióro, M., Medhi, D.: Routing, Flow and Capacity Design in Communication and Computer Networks. Morgan Kaufmann, San Francisco (2004)
Potters, J.A.M., Tijs, S.H.: The nucleolus of a matrix game and other nucleoli. Math. of Oper. Res. 17, 164–174 (1992)
Rawls, J.: The Theory of Justice. Harvard University Press, Cambridge (1971)
Rice, J.R.: Tschebyscheff approximation in a compact metric space. Bull. Amer. Math. Soc. 68, 405–410 (1962)
Yager, R.R.: On the analytic representation of the Leximin ordering and its application to flexible constraint propagation. Eur. J. Opnl. Res. 102, 176–192 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ogryczak, W., Śliwiński, T. (2006). On Direct Methods for Lexicographic Min-Max Optimization. In: Gavrilova, M., et al. Computational Science and Its Applications - ICCSA 2006. ICCSA 2006. Lecture Notes in Computer Science, vol 3982. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11751595_85
Download citation
DOI: https://doi.org/10.1007/11751595_85
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34075-1
Online ISBN: 978-3-540-34076-8
eBook Packages: Computer ScienceComputer Science (R0)