Reference Point Method with Lexicographic Min-Ordering of Individual Achievements
The reference point method (RPM) is a very effective technique for interactive analysis of the multiple criteria optimization problems. It provides the DM with a tool for an open analysis of the efficient frontier either connected or disconnected. The interactive analysis is navigated by the commonly accepted control parameters expressing reference levels for the individual objective functions. The individual achievement functions quantify the DM's satisfaction from the individual outcomes with respect to the given reference levels. The final scalarizing function is built as the augmented max-min aggregation of individual achievements which means that the worst individual achievement is essentially maximized but the optimization process is additionally regularized with the term representing the average achievement. The regularization by the average achievement is easily implementable but it may disturb the basic max-min aggregation. In order to avoid inconsistencies caused by the regularization, the max-min solution may be regularized according to the lexicographic min-order thus leading to the nucleolar RPM model. The nucleolar RPM implements a consequent max-min aggregation taking into account also the second-worst achievement, the third-worse and so on, thus resulting in much better modeling of the reference levels concept. The lexicographic min-ordering regularization is more complicated in implementation due to the requirement of point-wise ordering of partial achievements. Nevertheless, by taking advantage of piecewise linear expression of the cumulated ordered achievements, the nucleolar RPM can be formulated as a standard lexicographic optimization. Actually, in the case of concave piecewise linear partial achievement functions (typically used in the RPM), the resulting formulation extends the original constraints and criteria with simple linear inequalities thus allowing for a quite efficient implementation. It can be also approximated with the analytic form using the ordered weighted averages. The paper analyzes both the theoretical and practical issues of the nucleolar RPM.(original abstract)
- Behringer F.A.: A Simplex Based Algorithm for the Lexicographically Extended Linear Maxmin Problem. "European Journal of Operational Research" 1981, 7, pp. 274-283.
- Ehrgott M.: Discrete Decision Problems, Multiple Criteria Optimization Classes and Lexicographic Max-Ordering. In: Trends in Multicriteria Decision Making. Eds T.J. Stewart and R.C. van den Honert. Springer, Berlin 1998, pp. 31-44.
- Granat J. and Makowski M.: ISAAP - Interactive Specification and Analysis of Aspiration-Based Preferences. "European Journal of Operational Research" 2000, 122, pp. 469-485.
- Kostreva M.M., Ogryczak W., and Wierzbicki A.: Equitable Aggregations and Multiple Criteria Analysis. "European Journal of Operational Research" 2004, 158, pp. 362-367.
- Lewandowski A. and Wierzbicki A.P.: Aspiration Based Decision Support Systems - Theory, Software and Applications. Springer, Berlin 1989.
- Luss H.: On Equitable Resource Allocation Problems: A Lexicographic Minimax Approach. "Operations Research" 1999, 47, pp. 361-378.
- Marchi E. and Oviedo J.A.: Lexicographic Optimality in the Multiple Objective Linear Programming: The Nucleolar Solution. "European Journal of Operational Research" 1992, 57, pp. 355-359.
- Miettinen K. and Mäkelä M.M.: On Scalarizing Functions in Multiobjective Optimization. "OR Spectrum" 2002, 24, pp. 193-213.
- Ogryczak W.: Linear and Discrete Optimization with Multiple Criteria: Preference Models and Applications to Decision Support (in Polish). Warsaw University Press, Warsaw 1997.
- Ogryczak W.: On the Lexicographic Minimax Approach to Location Problems. "European Journal of Operational Research" 1997a, 100. pp. 566-585.
- Ogryczak W.: Preemptive Reference Point Method. In: Multicriteria Analysis - Proceedings of the XIth International Conference on MCDM. Ed. J. Climaco. Springer, Berlin 1997b, pp. 156-167.
- Ogryczak W.: Multiple Criteria Linear Programming Model for Portfolio Selection. "Annals of Operations Research" 2000, 97, pp. 143-162.
- Ogryczak W.: On Goal Programming Formulations of the Reference Point Method. "Journal of the Operational Research Society" 2001, 52, pp. 691-698.
- Ogryczak W. and Lahoda S.: Aspiration/Reservation Decision Support - A Step Beyond Goal Programming. "Journal of Multi-Criteria Decision Analysis" 1992, 1, pp. 101-117.
- Ogryczak W., Studziński K., and Zorychta K.: DINAS: A Computer-Assisted Analysis System for Multiobjective Transshipment Problems with Facility Location. "Computers and Operations Research" 1992, 19, pp. 637-647.
- Ogryczak W. and Śliwiński T.: On Solving Linear Programmes with the Ordered Weighted Averaging Objective. "European Journal of Operational Research" 2003, 148, pp. 80-91.
- Ogryczak W. and Tamir A.: Minimizing the Sum of the k Largest Functions in Linear Time. "Information Processing Letters" 2003, 85, pp. 117-122.
- Steuer R.E.: Multiple Criteria Optimization: Theory, Computation & Applications. Wiley, New York 1986.
- Strabski T. and Ogryczak W.: Nucleolar Reference Point Method (in Polish). In: Eds J. Kacprzyk, and R. Budziński: Badania Operacyjne i Systemowe 2006 - Metody i techniki. Exit, Warszawa 2006, s. 59-67.
- Wierzbicki A.P.: A Mathematical Basis for Satisficing Decision Making. "Mathematical Modelling" 1982, 3, pp. 391-405.
- Wierzbicki A.P., Makowski M., and Wessels J.: Model Based Decision Support Methodology with Environmental Applications. Kluwer, Dordrecht 2000.
- Yager R.R.: On the Analytic Representation of the Leximin Ordering and Its Application to Flexible Constraint Propagation. "European Journal of Operational Research" 1997, 102, pp. 176-192.