On two stability types for a multicriteria integer linear programming problem

Vladimir A. Emelichev ; Sergey E. Bukhtoyarov

Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 1 (2020), pp. 17-30.

Résumé

We consider a multicriteria integer linear programming problem with a parametrized optimality principle which is implemented by means of partitioning the partial criteria set into non-empty subsets, inside which relations on the set of solutions are based on the Pareto minimum. The introduction of this principle allows us to connect such classical selection functions as Pareto and aggregative-extremal. A quantitative analysis of two types of stability of the problem to perturbations of the parameters of objective functions is given under the assumption that an arbitrary $l_p$-Hölder norm, $1\leq p\leq\infty,$ is given in the solution space, and the Chebyshev norm is given in the criteria space. The formulas for the radii of quasistability and strong quasi-stability are obtained. Criteria of these types of stability are given as corollaries.

Bibliographie

[1] Pareto V., Manuel d'economie politique, V. Giard E. Briere, Paris, 1909

[2] Sholomov L. A., Logical methods for investigating discrete models of choice, Nauka, M., 1989 | MR

[3] Yudin D. B., Computational methods in decision making theory, Nauka, M., 1989 | MR

[4] Miettinen K., Nonlinear multiobjective optimization, Kluwer Academic Publishers, Boston, 1999 | MR | Zbl

[5] Emelichev V. A., Podkopaev D. P., “On a quantitive measure of stability for a vector problem in integer programming”, Comp. Math. and Math. physiscs, 38:11 (1998), 1727–1731 | MR | Zbl

[6] Emelichev V. A., Podkopaev D. P., “Stability and regularization of vector problems of integer linear programming”, Dicrete Analysis and Operation Research, Ser. 2, 8:1 (2001), 47–69 | MR | Zbl

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

[8] Emelichev V. A., Podkopaev D. P., “Quantitative stability analysis for vector problems of 0–1 programming”, Dicrete Optimization, 7:1-2 (2010), 48–63 | DOI | MR | Zbl

[9] Emelichev V., Nikulin Yu., “On a quasistability radius for multicriteria integer linear programming problem of finding extremum solutions”, Cybernetics and System Analysis, 55:6 (2019), 949–957 | DOI | MR | Zbl

[10] Sergienko I. V., Shilo V. P., Discrete optimization problems. Problems, methods, research, Naukova dumka, Kiev, 2003

[11] Emelichev V. A., Kotov V. M., Kuzmin K. G., Lebedeva N. T., Semenova N. V., “Stability and effective algorithms for solving multiobjective discrete optimization problems with incomplete information”, J. of Automation and Inf. Sciences, 46:2 (2014), 27–41 | DOI | MR

[12] Hardy G., Littlewood J., Polya G., Inequalities, University Press, Cambridge, 1988 | MR | Zbl

[13] Emelichev V. A., Gurevsky E. E., Platonov A. A., “On stability and quasi-stability radii for a vector combinatorial problem with a parametric optimality principle”, Bul. Acad. Ştiinţe Repub. Moldova, Mat., 2009, no. 2(60), 55–61 | MR | Zbl

[14] Smale S., “Global analysis and economics V: Pareto theory with constraints”, J. of Mathematical Economics, 1:3 (1974), 213–221 | DOI | MR | Zbl

[15] Kolmogorov A. N., Fomin S. V., Elements of the theory of functions and functional analysis, Fizmatlit, M., 2009 | MR

[16] Suhubi E., Functional analysis, Springer, Dordrecht, 2003 | MR

[17] Bukhtoyarov S. E., Emelichev V. A., “Optimality principle parametrization (from Pareto to Slater) and stability of multicriteria trajectory problems”, Dicrete Analysis and Operation Research, Ser. 2, 10:2 (2003), 3–18 | MR

[18] Bukhtoyarov S. E., Emelichev V. A., Stepanishina Yu. V., “Stability of discrete vector problems with the parametric privciple of optimality”, Cybernetics and systems analysis, 39:4 (2003), 604–614 | DOI | MR | Zbl

[19] Bukhtoyarov S. E., Emelichev V. A., “On stability of Nash equilibrium situations and Pareto optimal situations in finite games”, Computer Science Journal of Moldova, 11:1 (2003), 28–34 | MR | Zbl

[20] Bukhtoyarov S. E., Yemelichev V. A., “Quasistability of vector trajectory problem with the parametric optimality principle”, Russian Mathematics-New York, 48:1 (2004), 23–27 | MR | Zbl

[21] Emelichev V. A., Kuzmin K. G., “Finite cooperative games with a parametric concept of equilibrium under uncertainty conditions”, J. of Computer and Systems Sciences International, 45:2 (2006), 276–281 | DOI | MR | Zbl

[22] Emelichev V. A., Bukhtoyarov S. E., “Measure of stability for a finite cooperative game with a parametric optimality principle (from Pareto to Nash)”, Computational Mathematics and Mathematical Physics, 46:7 (2006), 1193–1199 | DOI | MR

[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”, Bul. Acad. Ştiinţe Repub. Moldova, Mat., 2008, no. 2(57), 58–67 \smallskip | MR | Zbl

[24] Emelichev V. A., Gurevky E. E., Platonov A. A., “Measure of stability for a finite cooperative game with a generalized concept of equilibrium”, Bul. Acad. Ştiinţe Repub. Moldova, Mat., 2006, no. 3(52), 17–26 | MR | Zbl

[25] Emelichev V. A., Karelkina O. V., “Finite cooperative games: Parametrisation of the concept of equilibrium (from Pareto to Nash) and stability of the efficient situation in the Hölder metric”, Discr. Math. Appl., 19:3 (2009), 229–236 | MR | Zbl