Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Archive
Cybernetics And Systems Analysis
International Theoretical Science Journal
UDC 519.8
V. Emelichev1, Yu. Nikulin2


1 Department of Mathematical Cybernetics, Mechanics and Mathematics Faculty, Belarusian State University, Minsk, Belarus

vemelichev@gmail.com

2 Department of Mathematics and Statistics, Faculty
of Science and Engineering, University of Turku, Finland

yurnik@utu.fi

ON A QUASISTABILITY RADIUS FOR MULTICRITERIA INTEGER
LINEAR PROGRAMMING PROBLEM OF FINDING EXTREMUM SOLUTIONS

Abstract. We consider a multicriteria integer linear programming problem with a targeting set of optimal solutions given by the set of all individual criterion minimizers (extrema). In this study, the lower and upper attainable bounds on the quasistability radius of the set of extremum solutions are obtained when solution and criterion spaces are endowed with different Hlder’s norms. As a corollary, an analytical formula for the quasistability radius is obtained for the case where criterion space is endowed with Chebyshev’s norm. Some computational challenges are also discussed.

Keywords: integer linear programming, multicriteria optimization, extremum solutions, Pareto optimality, stability analysis, quasistability radius, Hlder’s norms, Chebyshev’s norm.



FULL TEXT

REFERENCES

  1. Hadamard J. Lectures on Cauchy’s problem in linear partial differential equations. New Haven: Yale University Press. 1923. 316 p.

  2. Sergienko I., Shilo I. Discrete optimization problems: problems, methods of solution, research. Kyiv: Nauk. dumka, 2003. 264 p. (In Russian).

  3. Belousov E., Andronov V. Solvability and Stability for Problems of Polynomial Programming. Moscow: Moscow University Publisher, 1993.

  4. Sergienko I., Kozeratskaya L., T. Lebedeva: Stability and Parametric analysis of discrete optimization problems. Kyiv: Nauk. dumka, 1995. 168 p. (In Russian).

  5. Lebedeva T., Semenova N., Sergienko T. Stability of vector problems of integer optimization: relationship with the stability of sets of optimal and nonoptimal solutions. Cybernetics and Systems Analysis. 2005. Vol. 41, N 4. P. 551–558.

  6. Lebedeva T., Sergienko T. Stability of a vector integer quadratic programming problem with respect to vector criterion and constraints. Cybernetics and Systems Analysis. 2006. Vol. 42, N 5. P 667–674.

  7. Lebedeva T., Sergienko T. Different types of stability of vector integer optimization problem: general approach. Cybernetics and Systems Analysis. 2008. Vol. 44, N 3. P. 429–433.

  8. Lebedeva T., Semenova N., Sergienko T. Qualitative characteristics of the stability of vector discrete optimization problems with different optimality principles. Cybernetics and Systems Analysis. 2014. Vol. 50, N 2. P. 228–233.

  9. Lebedeva T., Semenova N., Sergienko T. Properties of perturbed cones ordering the set of feasible solutions of vector optimization problem. Cybernetics and Systems Analysis. 2014. Vol. 50, N 5. P. 712–717.

  10. Emelichev V., Kotov V., Kuzmin K., Lebedeva T., Semenova N., Sergienko T. Stability and effective algorithms for solving multiobjective discrete optimization problems with incomplete information. Journal of Automation and Information Sciences. 2014. Vol. 46, Iss. 2. P 27–41.

  11. Kuzmin K., Nikulin Y., Mkel M. On necessary and sufficient conditions of stability and quasistability in combinatorial multicriteria optimization. Control and Cybernetics. 2017. Vol. 46, N 4. P. 361–382.

  12. Leontev V. Discrete optimization. Journal of Computational Physics and Mathematics. 2007. Vol. 47, Iss. 2. P. 328–340.

  13. Gordeev E. Comparison of three approaches to studying stability of solutions to problems of discrete optimization and computational geometry. Journal of Applied and Industrial Mathematics. 2015. Vol. 9, Iss. 3. P. 358–366.

  14. Emelichev V., Podkopaev D. On a quantitative measure of stability for a vector problem in integer programming. Journal of Computational Physics and Mathematics. 1998 Vol. 38, Iss. 11. P. 1727–1731.

  15. Emelichev V., Podkopaev D. Stability and regularization of vector problems of integer linear programming. Diskretnyi Analiz i Issledovanie Operatsii. Ser. 2. 2001. Vol. 8, N 1. P. 47–69.

  16. Emelichev V., Girlich E., Nikulin Y., Podkopaev D. Stability and regularization of vector problems of integer linear programming. Optimization. 2002. Vol. 51, N 4. P. 645–676.

  17. Emelichev V., Podkopaev D. Quantitative stability analysis for vector problems of 0-1 programming. Discrete Optimization. 2010. Vol. 7, Iss. 1–2. P. 48–63.

  18. Emelichev V., Kuzmin K. Stability radius of a vector integer linear programming problem: case of a regular norm in the space of criteria. Cybernetics and Systems Analysis. 2010. Vol. 46, N 1. P. 72–79.

  19. Emelichev V., Korotkov V. Stability radius of a vector investment problem with Savage’s minimax risk criteria. Cybernetics and Systems Analysis. 2012. Vol. 48, N 3. P. 378–386.

  20. Bukhtoyarov S., Emelichev V. On the stability measure of solutions to a vector version of an investment problem. Journal of Applied and Industrial Mathematics. 2015. Vol. 9, Iss. 3. P. 328–334.

  21. Libura M., Nikulin Y. Stability and accuracy functions in multicriteria linear combinatorial optimization problem. Annals of Operations Research. 2006. Vol. 147, Iss. 1. P 255–267.

  22. Nikulin Y. Stability and accuracy functions in a coalition game with bans, linear payoffs and antagonistic strategies. Annals of Operations Research. 2009. Vol. 172, N 1. P 25–35.

  23. Sotskov Y., Sotskova N., Lai T., Werner F. Scheduling under uncertainty, theory and algorithms. Minsk: Belaruskaya nauka, 2010. 328 p.

  24. Nikulin Y. Accuracy and stability functions for a problem of minimization a linear form on a set of substitutions. In: Sequencing and Scheduling with Inaccurate Data. Sotskov Y. and Werner F. (Eds). Nova Science Pub Inc., 2014. Ch. 15. P. 409–426.

  25. Emelichev V., Platonov A. Measure of quasistability of a vector integer linear programming with generalized principle of optimality in the Hlder metric. Buletine of Academy of Sciences of Moldova. Mathematics. 2008. Vol. 57(2). P. 58–67.

  26. Emelichev V., Kuzmin K. A general approach to studying the stability of a Pareto optimal solution of a vector integer linear programming problem. Discrete Mathematics and Applications. 2007. Vol. 17, Iss. 4. P. 349–354.

  27. Emelichev V., Kuzmin K. On a type of stability of a multicriteria integer linear programming problem in the case of monotonic norm. Journal of Computers and Systems Sciences International. 2007. Vol. 46, N 5. P. 714–720.

  28. Podinovskii V., Noghin V. Pareto-optimal solutions of multicriteria problems. Moscow: Fizmatlit, 2007. 256 p.

  29. Sholomov L. Logical methods for investigation of the discrete choice models. Moscow: Nauka, 1989. 288 p.

  30. Yudin D. Computational methods in decision making. Moscow: Nauka, 1989. 320 p.

  31. Aizerman M., Aleskerov F. Choice of alternatives: theoretical foundations. Moscow: Nauka, 1990.

  32. Lotov A., Pospelova I. Multicriteria decision making problems. Moscow: MAKS Press, 2008. 197 p.

  33. Pareto V. Manuel D’ecoonomie Politique. Paris: V. Giard & E. BriЩre, 1909. 695 p.

  34. Slater M. Lagrange multipliers revisited. cowles commission discussion Paper 80. Mathematics 1950; In: Traces and Emergence of Nonlinear Programming. Giorgi G. and Kjeldsen T. (Eds.). Basel: Birkhuser, 2014. P. 293–306.

  35. Steuer R.E. Multiple criteria optimization: theory, computation and application. New York: John Wiley &Sons, 1986. 546 p.

  36. Miettinen K. Nonlinear multiobjective optimization. Boston: Kluwer Academic Publishers, 1999. 293 p.

  37. Noghin V. Reduction of the Pareto set: an axiomatic approach (studies in systems, decision and control). Cham: Springer, 2018. 232 p.

  38. Hardy G., Littlewood J., Polya G. Inequalities. Cambridge: Cambridge University Press, 1988. 338 p.

  39. Tikhonov A., Arsenin V. Solutions of ill-posed problems. Washington; Winston; New York: distributed solely by Halsted Press, 1977 . 255 p.

  40. Kolmogorov A., Fomin S. Elements of the theory of functions and functional analysis. Moscow: Fizmatlit, 2009. 570 p.

  41. Smale S. Global analysis and economics V: Pareto theory with constraints. Journal of Mathematical Economics. 1974. Vol. 1, Iss. 3. P. 213–221.

  42. Nikulin Y., Karelkina O., Mkel M.M. On accuracy, robustness and tolerances in vector Boolean optimization. European Journal of Operational Research. 2013. Vol. 224, Iss. 3. P. 449–457.

  43. Chakravarti N., Wagelmans A. Calculation of stability radius for combinatorial optimization problems. Oper. Res. Lett. 1998. Vol. 23, Iss. 1–2. P. 1–7.

  44. Ehrgott M. Multicriteria optimization. Berlin; Heidelberg: Springer-Verlag, 2005. 323 p.

  45. Kuzmin K. A general approach to the calculation of stability radii for the max-cut problem with multiple criteria. Journal of Applied and Industrial Mathematics. 2015. 9(4). P. 527–539.

  46. Roland J., Smet Y., Figueira J. On the calculation of stability radius for multi-objective combinatorial optimization problems by inverse optimization. 4OR-Q. J. Oper. Res. 2102. Vol. 10, Iss. 4. P 379–389.
© 2019 Kibernetika.org. All rights reserved.