Qualitative stability analysis of multicriteria combinatorial minimin problems

• Autorzy: Emelichev V. A. , Karelkina O. V. , Kuzmin K. G.
• Języki publikacji: EN

Abstrakty

EN

A multicriteria combinatorial problem with minimin partial criteria is considered. Necessary and sufficient conditions for the five known stability types of the problem are obtained. These stability types describe in different ways the behavior of the Pareto and lexicographic sets of the problem under initial data perturba- tions of the vector criteria.

Słowa kluczowe

EN

combinatorial optimization; Pareto set; lexicographic set; stability analysis; stability types

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2012
• Tom: Vol. 41, no. 1
• Strony: 57--79
• Opis fizyczny: Bibliogr. 29 poz.

Twórcy

autor

Emelichev V. A.

autor

Karelkina O. V.

autor

Kuzmin K. G.

• Mechanics and Mathematics Faculty, Belarusian State University av. Nezavisimosti 4, 220030 Minsk, Belarus,

Bibliografia

• Chakravarti, N. and Wagelmans, A. (1998) Calculation of stability radius for combinatorial optimization. Operations Research Letters, 23 (1), 1-7.
• Christofides, N. (1975) Graph theory. An algorithmic approach. Academic Press, New York.
• Daskin, M.S. (1995) Network and discrete location: models, algorithms and applications. John Wiley and Sons, New York.
• Ehrgott, M. and Gandibleux, X. (2000) A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spectrum 22 (4), 425-460.
• Ehrgott, M. (2005) Multicriteria Optimization. Second Edition. Springer, Berlin-Heidelberg.
• Emelichev, V.A., Girlich, E., Nikulin, Yu.V. and Podkopaev, D.P. (2002) Stability and regularization of vector problem of integer linear programming. Optimization 51 (4), 645-676.
• Emelichev, V.A., Krichko, V.N. and Nikulin, Yu.V. (2004) The stability radius of an efficient solution in minimax Boolean programming problem. Control and Cybernetics 33 (1), 127-132.
• Emelichev, V.A., Kuzmin, K.G. and Nikulin, Yu.V. (2005) Stability analysis of the Pareto optimal solution for some vector Boolean optimization problem. Optimization 54 (6), 545-561.
• Emelichev, V.A. and Gurevsky, E.E. (2007) On stability of some lexicographic multicriteria Boolean problem. Control and Cybernetics 36 (2), 333-346.
• Emelichev, V.A. and Kuzmin, K.G. (2008) Stability criteria in vector combinatorial bottleneck problems in terms of binary relations. Cybernetics and Systems Analysis, 44 (3), 397-404.
• Emelichev, V.A., Karelkina, O.V. and Girlich, E. (2009) Postoptimal analysis of multicriteria combinatorial center location problem. Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica (61), 13-29.
• Emelichev, V.A., Gurevsky, E.E. and Kuzmin, K.G. (2010a) On stability of some lexicographic integer optimization problem. Control and Cybernetics 39 (3), 811-826.
• Emelichev, V. and Podkopaev, D. (2010b) Quantitative stability analysis for vector problems of 0-1 programming. Discrete Optimization 7 (1-2), 48-63.
• Emelichev, V.A. and Karelkina, O.V. (2011) Postoptimal analysis of the multicriteria combinatorial median location problem. Optimization. DOI: 10.1080/02331934.2010.542813.
• Greenberg, H.J. (1998) An annotated bibliography for post-solution analysis in mixed integer and combinatorial optimization. In: D.L. Woodruff, ed., Advances in Computational and Stochastic Optimization, Logic Programming and Heuristic Search. Kluwer Academic Publishers, Boston, 97-148.
• van Hoesel, S. and Wagelmans, A. (1999) On the complexity of postoptimality analysis of 0-1 programs. Discrete Applied Mathematics 91 (1-3), 251-263.
• Kozeratska, L., Forbes, J.F., Goebel, R.G. and Kresta, J.V. (2004) Perturbed cones for analysis of uncertain Multi-criteria optimization problems. Linear Algebra and its Applications 378, 203-229.
• Lebedeva, T.T., Semenona N.V. and Sergienko, T.I. (2005) Stability of vector problems of integer optimization: relationship with the stability of sets of optimal and nonoptimal solutions. Cybernetics and Systems Analysis, 41 (4), 551-558.
• Lebedeva, T.T. and Sergienko, T.I. (2008) Different types of stability of vector integer optimization problem: general approach. Cybernetics and Systems Analysis, 44 (3), 429-433.
• Libura, M., van der Poort, E.S., Sierksma, G. and van der Veen, J.A.A. (1998) Stability aspects of the traveling salesman problem based on k-best solutions. Discrete Applied Mathematics 87 (1-3), 159-185.
• Libura, M. and Nikulin, Y. (2004) Stability and accuracy functions in multicriteria combinatorial optimization problem with Σ-MINMAX and Σ-MINMIN partial criteria. Control and Cybernetics 33 (3), 511-524.
• Libura, M. (2007) On the adjustment problem for linear programs. European Journal of Operational Research 183 (1), 125-134.
• Miettinen, K. (1999) Nonlinear Multiobjective Optimization. Kluwer Acad. Publ., Boston.
• Sergienko, I.V. and Shilo, V.P. (2003) Discrete Optimization Problems (in Russian). Naukova dumka, Kiev.
• Slater, M. (1950) Lagrange multipliers revisited: a contribution to nonlinear programming. Cowles commission discussion paper, Mathematics (403).
• Smale, S. (1974) Global analysis and economics V: Pareto theory with constraints. Journal of Mathematical Economics (1), 213 - 221.
• Sotskov, Yu.N., Leontev, V.K. and Gordeev, E.N. (1995) Some concepts of stability analysis in combinatorial optimization. Discrete Applied Mathematics 58 (2), 169-190.
• Suhubi, E. (2003) Functional Analysis. Springer.
• Tanino, T. (1988) Sensitivity analysis in multiobjective optimization. Journal of Optimization Theory and Applications 56 (3), 479-499.