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

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.

• Yury Nikulin

• Stability and accuracy
• multicriteria optimization
• lexicographic optimality.

[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.