Stability Analysis for a Multicriteria Problem with Linear Criteria and Parameterized Principle of Optimality “from Lexicographic to Slater“

Authors: Yury Nikulin

Abstract:

A multicriteria linear programming problem with integer variables and parameterized optimality principle "from lexicographic to Slater" is considered. A situation in which initial coefficients of penalty cost functions are not fixed but may be potentially a subject to variations is studied. For any efficient solution, appropriate measures of the quality are introduced which incorporate information about variations of penalty cost function coefficients. These measures correspond to the so-called stability and accuracy functions defined earlier for efficient solutions of a generic multicriteria combinatorial optimization problem with Pareto and lexicographic optimality principles. Various properties of such functions are studied and maximum norms of perturbations for which an efficient solution preserves the property of being efficient are calculated.

Keywords: Stability and accuracy, multicriteria optimization, lexicographic optimality.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1333813

References:

[1] M. Ehrgott, Multicriteria optimization, Springer, Berlin, 2005.
[2] V. Emelichev, E. Girlich, Y. Nikulin and D. Podkopaev, (2002). "Stability and regularization of vector problems of integer linear programming". Optimization 51, 645 - 676.
[3] V. Emelichev, A. Platonov, (2006). "About one discrete analog of Hausdorff semi-continuity of suitable mapping in a vector combinatorial problem with a parametric principle of optimality ("from Slater to lexicographic")". Revue dAnalyse Numerique et de Theorie de lApproximation 35.
[4] H. Greenberg, (1998). "An annotated bibliography for post-solution analysis in mixed integer and combinatorial optimization." In D. Woodruff (ed.) Advances in computational and stochastic optimization, Logic programming and heuristic search, 97 - 148. Dordrecht: Kluwer Academic Publishers.
[5] M. Libura, (1999). "On accuracy of solution for combinatorial optimization problems with perturbed coefficients of the objective function". Annals of Operation Research 86, 53 - 62.
[6] M. Libura, (2000). "Quality of solutions for perturbed combinatorial optimization problems". Control and Cybernetics 29, 199 - 219.
[7] M. Libura and Y. Nikulin, (2006). "Stability and accuracy functions in multicriteria linear combinatorial optimization problems". Annals of Operations Research 147, 255 - 267.
[8] M. Libura, (2007). "On the robustness of optimal solutions for combinatorial optimization problems". Research Report 2/2007, Systems Research Institute, Polish Academy of Sciences.
[9] M. Libura, (2008). "Robustness tolerances for combinatorial optimization problems". Research Report 4/2008, Systems Research Institute, Polish Academy of Sciences.
[10] K. Miettinen, Nonlinear Multiobjective Optimization (Kluwer Academic Publishers, Boston, 1999).
[11] Y. Nikulin, (2008). "Stability and accuracy functions in a coalition game with bans, linear payoffs and antagonistic strategies". (to appear in Annals of Operations Research)
[12] Y. Nikulin and M.M. M¨akel¨a, (2008). "Quantitative measures of solution robustness in a parametrized multicriteria zero-one linear programming problem". Turku Center for Computer Science, Technical Report 917.