Aspects of stability for multicriteria quadratic problems of Boolean programming

Vladimir A. Emelichev ; Yury V. Nikulin

Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 2 (2018), pp. 30-40.

Résumé

We consider a multicriteria Boolean programming problem of finding the Pareto set. Partial criteria are given as quadratic functions, and they are exposed to independent perturbations. We study quantitative characteristic of stability (stability radius) of the problem. The lower and upper bounds for the stability radius are obtained in the situation where solution space and problem parameter space are endowed with various Hölder's norms.

Bibliographie

[1] Sergienko I. V., Shilo V. P., Discrete optimization problems. Problems, methods of solutions, investigations, Naukova dumka, Kiev, 1979

[2] Emelichev V. A., Girlich E., Nikulin Y. V., PodkopaevD. P., “Stability and regularization of vector problems of integer linear programming”, Optimization, 51:4 (2002), 645–676 | DOI | MR | Zbl

[3] Emelichev V. A., Kuzmin 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

[4] Libura M., Nikulin Y. V., “Stability and accuracy functions in multicriteria linear combinatorial optimization problems”, Annals of Operations Research, 147 (2007), 255–267 | DOI | MR

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

[6] Emelichev V. A., Kuzmin K. G., “Stability radius of a vector integer linear programming problem: case of a regular norm in the space of criteria”, Cybernetics and Systems Analysis, 46:1 (2010), 72–79 | DOI | MR | Zbl

[7] Emelichev V. A., Kuzmin K. G., Mychkov V. I., “Estimates of stability radius of multicriteria Boolean problem with Holder metrics in parameter spaces”, Bul. Acad. Ştiinţe Repub. Moldova, Mat., 2015, no. 2(78), 74–81 | MR | Zbl

[8] Libura M., Nikulin Y. V., “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

[9] Emelichev V. A., Korotkov V. V., “On stability radius of the multicriteria variant of Markowitz's investment portfolio problem”, Bul. Acad. Ştiinţe Repub. Moldova, Mat., 2011, no. 1(65), 83–94 | MR | Zbl

[10] Emelichev V. A., Korotkov V. V., “Stability radius of a vector investment problem with Savage's minimax risk criteria”, Cybernetics and Systems Analysis, 48:3 (2012), 378–386 | DOI | MR | Zbl

[11] Emelichev V. A., Korotkov V. V., “On stability of a vector Boolean investment problem with Wald's criteria”, Discrete Math. Appl., 22:4 (2012), 367–381 | DOI | MR | Zbl

[12] Emelichev V. A., Korotkov V. V., “On stability of multicriteria investment Boolean problem with Wald's efficiency criteria”, Bul. Acad. Ştiinţe Repub. Moldova, Mat., 2014, no. 1(74), 3–13 | MR | Zbl

[13] Korotkov V. V., Nikulin Y. V., Emelichev V. A., “Stability of the bicriteria Boolean investment problem subject to extreme optimism and pessimism criteria”, Croatian Operation Research Review, 6:1 (2015), 195–205 | DOI | MR | Zbl

[14] Bukhtoyarov S. E., Emelichev V. A., “On the stability measure of solutions to a vector version of an investment problem”, Journal of Applied and Industrial Mathematics, 9:3 (2015), 328–334 | DOI | MR | Zbl

[15] Shor N. Z., Stetsenko S. I., Quadratic extreme problems and non-differential optimization, Naukova dumka, Kiev, 1989

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

[17] Ehrgott M., Multicriteria optimization, Springer, Berlin, 2005 | MR | Zbl

[18] Barahona F., Grötschel M., Jünger M., Reinelt G., “An application of combinatorial optimization to statistical physics and circuit layout design”, Operation Research, 36 (1988), 491–513 | DOI

[19] Phillips A. T., Rosen J. S., “A quadratic assignment formulation of the molecular conformation problem”, Journal of Global Optimization, 4 (1994), 229–241 | DOI | MR | Zbl

[20] Chardaire P., Sutter A., “A decomposition method for quadratic zero-one programming”, Management Science, 41 (1995), 704–712 | DOI | Zbl

[21] Padberg M., “The boolean quadric polytope - some characteristics, facets and relatives”, Mathematical Programming, 45 (1989), 139–172 | DOI | MR | Zbl

[22] Pardalos P. M., Rodgers G. P., “A branch and bound algorithm for the maximum clique problem”, Computers and Operation Research, 19 (1992), 363–375 | DOI | Zbl

[23] Pardalos P. M., Xue J., “The maximum clique problem”, Journal of Global Optimization, 4 (1994), 301–328 | DOI | MR | Zbl

[24] Krarup J., Pruzan P. M., “Computer-aided Layot Design”, Mathematical Programming Study, 9 (1978), 75–94 | DOI | MR | Zbl

[25] Laughunn D. J., “Quadratic Binary Programming”, Operation Research, 14 (1970), 454–461 | DOI

[26] Markowitz H. M., Portfolio Selection: Efficient Diversification of Investments, John Wiley Sons, New York, 1959, (reprinted by Yale University Press, 1970) | MR

[27] Gallo G., Hammer P. L., Simeone B., “Quadratic Knapsack Problems”, Mathematical Programming, 12 (1980), 132–149 | MR | Zbl

[28] Ahmadian A., Kochenberger B. G., Alidaee B., “Quadratic Programming approach for the optimal solution of two Scheduling problems”, International Journal of Systems Science, 25 (1994), 401–408 | DOI | MR | Zbl

[29] Hardy G. H., Littlewood J. E., Polya G., Inequalities, 2nd ed., Cambridge University Press, Cambridge, 1952 | MR | Zbl

[30] Podinovskiy V. V., Nogin V. D., Pareto optimal solutions of multicriteria problems, Nauka, Moscow, 1982 | MR