Stability conditions for a multicriteria Boolean problem of minimizing projections of linear functions

V. A. Emelichev ; K. G. Kuz'min

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 19 (2013) no. 2, pp. 125-133

Résumé

We consider a multicriteria Boolean problem with partial criteria that are projections of linear functions on the nonnegative orthant. Necessary and sufficient conditions for five known types of stability of the problem are obtained. These types describe differently the behavior of the Pareto set of the problem with respect to disturbances of the parameters of the vector criterion.

Détail

Mots-clés : multicriteria problem
Keywords: projections of linear functions, Pareto set, types of stability.

Bibliographie

[1] Miettinen K., Nonlinear multiobjective optimization, Kluwer Acad. Publ., Boston, 1999, 328 pp. | MR | Zbl

[2] Sergienko I. V., Shilo V. P., Zadachi diskretnoi optimizatsii, Nauk. dumka, Kiev, 2003, 261 pp.

[3] Greenberg H. J., “An annotated bibliography for post-solution analysis in mixed integer programming and combinatorial optimization”, Advances in combinatorial and stochastic optimization. Logic programming and heuristic search, Kluwer Acad. Publ., Boston, 1998, 97–148 | DOI | MR

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

[5] Chakravarti N., Wagelmans A., “Calculation of stability radius for combinatorial optimization problems”, Oper. Res. Lett., 23:1–2 (1998), 1–7 | DOI | MR | Zbl

[6] Libura M., “On accuracy of solution for discrete optimization problems with perturbed coefficients of the objective function”, Ann. Oper. Res., 86 (1999), 53–62 | DOI | MR | Zbl

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

[8] Libura M., “On the adjustment problem for linear programs”, European J. Oper. Res., 183:1 (2007), 125–134 | DOI | MR | Zbl

[9] Kozeratska L. [et al.], “Perturbed cones for analysis of uncertain multi-criteria optimization problems”, Linear Algebra Appl., 378 (2004), 203–229 | DOI | MR | Zbl

[10] Emelichev V. A., Kuzmin K. G., “Analiz chuvstvitelnosti effektivnogo resheniya vektornoi bulevoi zadachi minimizatsii proektsii lineinykh funktsii na $\mathbf R_+$ i $\mathbf R_-$”, Diskret. analiz i issledovanie operatsii. Ser. 2, 12:2 (2005), 24–43 | MR | Zbl

[11] Emelichev V. A., Kuzmin K. G., “O radiuse ustoichivosti effektivnogo resheniya odnoi vektornoi zadachi buleva programmirovaniya v metrike $l_1$”, Dokl. RAN, 401:6 (2005), 733–735 | MR

[12] 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

[13] Emelichev V. A., Kuzmin K. G., “Obschii podkhod k issledovaniyu ustoichivosti pareto-optimalnogo resheniya vektornoi zadachi tselochislennogo lineinogo programmirovaniya”, Diskret. matematika, 19:3 (2007), 79–83 | DOI | MR | Zbl

[14] Sotskov Yu. N. [et al.], Scheduling under uncertainty. Theory and algorithms, Belorusskaya nauka, Minsk, 2010, 326 pp.

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

[16] Emelichev V. A., Korotkov V. V., Kuzmin K. G., “Mnogokriterialnaya investitsionnaya zadacha v usloviyakh neopredelennosti i riska”, Izv. RAN. Teoriya i sistemy upravleniya, 2011, no. 6, 157–164 | MR

[17] Emelichev V. A., Korotkov V. V., “Ustoichivost vektornoi investitsionnoi bulevoi zadachi s kriteriyami Valda”, Diskret. matematika, 24:3 (2012), 3–16 | DOI | MR | Zbl

[18] Emelichev V. A., Korotkov V. V., “Analiz ustoichivosti pareto-optimalnogo portfelya mnogokriterialnoi investitsionnoi zadachi s maksiminnymi kriteriyami Valda”, Diskret. analiz i issledovanie operatsii, 19:6 (2012), 23–36

[19] Emelichev V. A., Korotkov V. V., “Issledovanie ustoichivosti reshenii vektornoi investitsionnoi bulevoi zadachi v sluchae metriki Geldera v kriterialnom prostranstve”, Prikl. diskret. matematika, 2012, no. 4, 61–72

[20] Lebedeva T. T., Semenova N. V., Sergienko T. I., “Ustoichivost vektornykh zadach tselochislennoi optimizatsii: vzaimosvyaz s ustoichivostyu mnozhestva optimalnykh i neoptimalnykh reshenii”, Kibernetika i sistem. analiz, 2005, no. 4, 90–100 | MR | Zbl

[21] Lebedeva T. T., Sergienko T. I., “Raznye tipy ustoichivosti vektornoi zadachi tselochislennoi optimizatsii: obschii podkhod”, Kibernetika i sistem. analiz, 2008, no. 3, 142–148 | MR | Zbl

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

[23] Emelichev V. A., Gurevsky E. E., Kuzmin K. G., “On stability of some lexicographic integer optimization problem”, Control Cybernet., 39:3 (2010), 811–826 | MR

[24] Emelichev V. A., Kuzmin K. G., “Kriterii ustoichivosti vektornykh kombinatornykh zadach “na uzkie mesta” v terminakh binarnykh otnoshenii”, Kibernetika i sistem. analiz, 2008, no. 3, 103–111 | MR | Zbl

[25] Emelichev V. A., Korotkov V. V., Kuzmin K. G., “Postoptimalnyi analiz odnoi vektornoi minimaksnoi kombinatornoi zadachi”, Kibernetika i sistem. analiz, 2011, no. 3, 95–108 | MR

[26] Emelichev V., Karelkina O., “Postoptimal analysis of the multicriteria combinatorial median location problem”, Optimization, 61:9 (2012), 1151–1167 | DOI | MR | Zbl

[27] Emelichev V. A., Karelkina O. V., Kuzmin K. G., “Qualitative stability analysis of multicriteria combinatorial minimin problems”, Control Cybernet., 41:1 (2012), 57–79 | MR

[28] Eremin I. I., Mazurov V. D., Nestatsionarnye protsessy matematicheskogo programmirovaniya, Nauka, M., 1979, 288 pp. | MR

[29] Eremin I. I., Mazurov V. D., Astafev N. N., Nesobstvennye zadachi lineinogo i vypuklogo programmirovaniya, Nauka, M., 1983, 336 pp. | MR

[30] Berdnikova E. A., Eremin I. I., Popov L. D., “Raspredelennye feierovskie protsessy dlya sistem lineinykh neravenstv i zadach lineinogo programmirovaniya”, Avtomatika i telemekhanika, 2004, no. 2, 16–32 | MR | Zbl

[31] Smale S., “Global analisis and economics. V. Pareto theory with constraints”, J. Math. Econom., 1:3 (1974), 213–221 | DOI | MR | Zbl

[32] Slater M., Lagrange multipliers revisited, Cowles Foundation Discussion Paper 80, Cowles Foundation for Research in Economics at Yale University, 1959, 13 pp.

[33] Podinovskii V. V., Nogin V. D., Pareto-optimalnye resheniya mnogokriterialnykh zadach, Fizmatlit, M., 2007, 256 pp.

[34] Suhubi E., Functional analysis, Springer, Berlin, 2003, 702 pp. | Zbl

[35] Kolmogorov A. N., Fomin S. V., Elementy teorii funktsii i funktsionalnogo analiza, Fizmatlit, M., 2004, 572 pp.