Postoptimal analysis of multicriteria combinatorial center location problem

Vladimir Emelichev ; Eberhard Girlich ; Olga Karelkina

Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 3 (2009), pp. 13-29.

Résumé

A multicriteria variant of a well known combinatorial MINMAX location problem with Pareto and lexicographic optimality principles is considered. Necessary and sufficient conditions of an optimal solution stability of such problems to the initial data perturbations are formulated in terms of binary relations. Numerical examples are given.

Bibliographie

[1] Ehrgott M., Gandibleux X., “A survey and annotated bibliography of multiobjective combinatorial optimization”, OR Spectrum, 22:4 (2000), 425–460 | DOI | MR | Zbl

[2] Tanino T., Sawaragi Y., “Stability of nondominated solutions in multicriteria decision-making”, Journal of Optimization Theory and Applications, 30:2 (1980), 229–253 | DOI | MR | Zbl

[3] Sawaragi Y., Nakayama H., Tanino T., Theory of Multi-Objective Optimization, Academic Press, Orlando, 1985 | MR | Zbl

[4] Tanino T., “Sensitivity analysis in multiobjective optimization”, Journal of Optimization Theory and Applications, 56:3 (1988), 479–499 | DOI | MR | Zbl

[5] Fiacco A. V., Mathematical Programming with Data Perturbations, Marcel Dekker, New York, 1988 | MR

[6] Greenberg H. J., “An annotated bibliography for post-solution analysis in mixed integer and combinatorial optimization”, Advances in Computational and Stochastic Optimization, Logic Programming and Heuristic Search, ed. D. L. Woodruff, Kluwer Acad. Publ., Boston, MA, 1998, 97–148 | DOI | MR

[7] Chakravarti N., Wagelmans A., “Calculation of stability radius for combinatorial optimization”, Operations Research Letters, 23:1 (1998), 1–7 | DOI | MR | Zbl

[8] Sotskov Yu. N., Leontev V. K., Gordeev E. N., “Some concepts of stability analysis in combinatorial optimization”, Discrete Appl. Math., 58:2 (1995), 169–190 | DOI | MR | Zbl

[9] Libura M., van der Poort E. S., Sierksma G., van der Veen J. A. A., “Stability aspects of the traveling salesman problem based on $k$-best solutions”, Discrete Appl. Math., 87:1–3 (1998), 159–185 | DOI | MR | Zbl

[10] van Hoesel S., Wagelmans A., “On the complexity of postoptimality analysis of 0-1 programs”, Discrete Appl. Math., 91:1–3 (1999), 251–263 | MR | Zbl

[11] Sergienko I. V., Shilo V. P., Discrete optimization problems. Problems, methods of solutions, investigations, Naukova dumka, Kiev, 2003 (Russian)

[12] Kozeratska L., Forbes J. F., Goebel R. G., Kresta J. V., “Perturbed cones for analysis of uncertain multi-criteria optimization problems”, Linear Algebra and its Applications, 378 (2004), 203–229 | DOI | MR | Zbl

[13] Libura M., Nikulin Y., “Stability and accuracy functions in multicriteria combinatorial optimization problem with $\Sigma$–MINMAX and $\Sigma$–MINMIN partial criteria”, Control and Cybernetics, 33:3 (2004), 511–524 | MR | Zbl

[14] Libura M., “On the adjustment problem for linear programs”, European Journal of Operational Research, 183:1 (2007), 125–134 | DOI | MR | Zbl

[15] Sotskov Yu. N., Sotskova N. Yu., Scheduling theory. The systems with uncertain numerical parameters, National Academy of Sciences of Belarus, Minsk, 2004 (Russian)

[16] Emelichev V. A., Girlich E., Nikulin Yu. V., Podkopaev D. P., “Stability and regularization of vector problem of integer linear programming”, Optimization, 51:4 (2002), 645–676 | DOI | MR | Zbl

[17] Emelichev V. A., Krichko V. N., Nikulin Y. V., “The stability radius of an efficient solution in minimax Boolean programming problem”, Control and Cybernetics, 33:1 (2004), 127–132 | MR | Zbl

[18] Emelichev V. A., Kuzmin K. G., Nikulin Yu. V., “Stability analysis of the Pareto optimal solution for some vector Boolean optimization problem”, Optimization, 54:6 (2005), 545–561 | DOI | MR | Zbl

[19] Emelichev V. A., Kuz'min K. G., “On a type of stability of a multicriteria integer linear programming problem in the case of a monotone norm”, Journal of Computer and Systems Sciences International, 46:5 (2007), 714–720 | DOI | MR

[20] Emelichev V. A., Gurevsky E. E., “On stability of some lexicographic multicriteria Boolean problem”, Control and Cybernetics, 36:2 (2007), 333–346 | MR | Zbl

[21] Emelichev V. A., Kuzmin K. G., “On stability of a vector combinatorial problem with MINMIN criteria”, Discrete Math. Appl., 18:6 (2008), 557–562 | DOI | MR | Zbl

[22] Emelichev V. A., Kuzmin K. G., “Stability criteria in vector combinatorial bottleneck problems in terms of binary relations”, Cybernetics and systems analysis, 44:3 (2008), 397–404 | DOI | MR | Zbl

[23] Emelichev V. A., Platonov A. A., “Measure of quasistability of a vector integer linear programming problem with generalized principle of optimality in the Helder metric”, Buletinul Academiei de Stiinte a Republicii Moldova, Matematica, 2008, no. 2(57), 58–67 | MR | Zbl

[24] Christofides N., Graph theory. An algorithmic approach, Academic Press, New York, 1975 | MR | Zbl

[25] Zambitski D. K., Lozovanu D. D., Algorithms for solving network optimization problems, Shtiintsa, Kishinev, 1983 (Russian) | MR

[26] Mirchandani P., Francis R., Discrete location theory, John Wiley and Sons, New York, 1990 | MR | Zbl

[27] Daskin M. S., Network and discrete location: models, algorithms and applications, John Wiley and Sons, New York, 1995 | MR

[28] Ehrgott M., Multicriteria optimization, Second edition, Springer, Berlin–Heidelberg, 2005 | MR

[29] Emelichev V. A., Stepanishina Yu. V., “Quasistability of a vector nonlinear trajectory problem with the Pareto optimality principle”, Izv. Vusov. Matematika, 2000, no. 12, 27–32 (Russian) | MR | Zbl

[30] Emelichev V. A., Karelkina O. V., “Postoptimal analysis of one lexicographic combinatorial problem with non-linear criteria”, Computer Science Journal of Moldova, 17:1 (2009), 48–57 | MR | Zbl