vestifmИзвестия Национальной академии наук Беларуси. Серия физико-математических наукProceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series1561-24302524-2415The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"10.29235/1561-2430-2022-58-2-179-189vestifm-642Research ArticleМАТЕМАТИКАMATHEMATICSМера устойчивости многокритериальной задачи целочисленного линейного программирования с параметрическим принципом оптимальностиStability measure of multicriteria integer linear programming problem with a parametric optimality principleЕмеличевВ. А.EmelichevV. A.

Емеличев Владимир Алексеевич – доктор физико-математических наук, профессор

пр. Независимости, 4, 220030, Минск

Vladimir A. Emelichev – Dr. Sc. (Physics and Mathematics), Professor

4, Nezavisimosti Ave., 220030, Minsk

vemelichev@gmail.comБухтояровС. Е.BukhtoyarovS. E.

Бухтояров Сергей Евгеньевич – кандидат физико-математических наук, доцент

пр. Независимости, 4, 220030, Минск

Sergey E. Bukhtoyarov – Ph. D. (Physics and Mathematics), Associate Professor

4, Nezavisimosti Ave., 220030, Minsk

buser@tut.byБелорусский государственный университетBelarusian State University202205072022582179189Copyright © Емеличев В.А., Бухтояров С.Е., 20222022Емеличев В.А., Бухтояров С.Е.Emelichev V.A., Bukhtoyarov S.E.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestifm.belnauka.by/jour/article/view/642

Рассматривается многокритериальная задача целочисленного линейного программирования с параметрическим принципом оптимальности. Параметризация реализована путем разбиения множества критериев на несколько упорядоченных по важности непересекающихся групп (подмножеств) критериев с доминированием по Парето в пределах каждой группы. Введенный параметрический принцип оптимальности позволил связать такие классические принципы оптимальности, как лексикографический и паретовский. Для радиуса устойчивости, который является предельным уровнем возмущений параметров задачи, не приводящих к появлению новых оптимальных решений, получены верхняя и нижняя оценки в случае произвольных норм Гёльдера в критериальном пространстве и пространстве решений. Некоторые ранее известные результаты по устойчивости булевой задачи линейного программирования сформулированы в качестве следствий. 

In this paper, we consider a multicriteria integer linear programming problem with a parametric principle of optimality. Parameterization is realized by dividing the set of criteria into several disjoint groups (subsets) of criteria ordered by importance, with Pareto dominance within each group. The introduced parametric principle of optimality made it possible to connect such classical principles of optimality as lexicographic and Pareto ones. For the stability radius, which is the limiting level of perturbations of the parameters of the problem, not causing the appearance of new optimal solutions, the upper and lower estimations are obtained in the case of arbitrary Hölder’s norms in the criterion space and solution space. Some previously known results on the stability of the Boolean linear programming problem are formulated as corollaries.

многокритериальная задачазадача целочисленного линейного программированияпараметрический принцип оптимальностилексикографический принцип оптимальностиоптимальность по Пареторадиус устойчивостинорма Гёльдераmulticriteria probleminteger linear programming problemparametric principle of optimalitylexicographic principle of optimalityPareto optimalitystability radiusHölder’s normРабота выполнена при финансовой поддержке Белорусского республиканского фонда фундаментальных исследований в рамках проекта № Ф20УКА-005 «Дискретные структуры, корректность, алгоритмическая сложность задач дискретной оптимизации и теории графов».This work was supported by the Belarusian Republican Foundation for Basic Research within the framework of project no. Ф20УКА-005 “Discrete structures, correctness, algorithmic complexity of discrete optimization problems and graph theory”.ReferencesHadamard, J. Lectures on Cauchy’s problem in linear partial differential equations / J. Hadamard. – Yale: Yale University Press, 1923. – 338 p.Hadamard J. Lectures on Cauchy’s Problem in Linear Partial Differential Equations. Yale, Yale University Press, 1923. 338 p.Сергиенко, И. В. Исследование устойчивости и параметрический анализ дискретных оптимизационных задач / И. В. Сергиенко, Л. Н. Козерацкая, Т. Т. Лебедева. – Киев: Наук. думка, 1995. – 170 с.Sergienko I. V., Kozeratskaya L. N., Lebedeva T. T. Research of Stability and Parametric Analysis of Discrete Optimization Problems. Kyiv, Navukova dumka Publ., 1995. 168 p. (in Russian).Сергиенко, И. В. Задачи дискретной оптимизации. Проблемы, методы решения, исследования / И. В. Сергиенко, В. П. Шило. – Киев: Наук. думка, 2003. – 261 с.Sergienko I. V., Shilo V. P. Discrete Optimization Problems. Problems, Methods, Research. Kiev, Naukova dumka Publ., 2003. 261 p. (in Russian).Устойчивость и эффективные алгоритмы решения задач дискретной оптимизации с многими критериями и неполной информацией / В. А. Емеличев [и др.] // Проблемы управления и информатики. – 2014. – № 1. – С. 53–67.Emelichev V. A., Kotov V. M., Kuzmin K. G., Lebedeva T. T., Semenova N. V., Sergienko T. I. Stability and effective algorithms for solving multiobjective discrete optimization problems with incomplete information. Journal of Automation and Information Sciences, 2014, vol, 46, no. 2, pp. 27–41. https://doi.org/10.1615/JAutomatInfScien.v46.i2.30Лебедева, Т. Т. Разные типы устойчивости векторной задачи целочисленной оптимизации: общий подход / Т. Т. Лебедева, Т. И. Сергиенко // Кибернетика и систем. анализ. – 2008. – Т. 44, № 3. – С. 142–148.Lebedeva T. T., Sergienko T. I. Different types of stability of vector integer optimization problem: General approach. Cybernetics and Systems Analysis, 2008, vol. 44, no. 3, pp. 429–433. https://doi.org/10.1007/s10559-008-9017-9Kuzmin, K. On necessary and sufficient conditions of stability and quasistability in combinatorial multicriteria optimization / K. Kuzmin, Yu. Nikulin, M. Makela // Control and Cybernetics. – 2017. – Vol. 46, № 4. – P. 361–382.Kuzmin K., Nikulin Yu., Makela M. On necessary and sufficient conditions of stability and quasistability in combinatorial multicriteria optimization. Control and Cybernetics, 2017, vol. 46, no. 4, pp. 361–382.Леонтьев, В. К. Дискретная оптимизация / В. К. Леонтьев // Журн. вычисл. математики и мат. физики. – 2007. – Т. 47, № 2. – С. 338–352.Leont'ev V. K. Discrete optimization. Computational Mathematics and Mathematical Physics, 2007, vol. 47, no. 2, pp. 328–340. https://doi.org/10.1134/S0965542507020157Емеличев, В. А. О радиусе устойчивости векторной инвестиционной задачи с критериями минимаксного риска Сэвиджа / В. А. Емеличев, В. В. Коротков // Кибернетика и систем. анализ. – 2012. – Т. 48, № 3. – С. 68–77.Emelichev V. A., Korotkov V. V. Stability radius of a vector investment problem with Savage's minimax risk criteria. Cybernetics and Systems Analysis, 2012, vol. 48, no. 3, pp. 378–386. https://doi.org/10.1007/s10559-012-9417-8Емеличев, В. А. Постоптимальный анализ векторного варианта одной инвестиционной задачи / В. А. Емеличев, В. И. Мычков // Тр. Ин-та математики. – 2016. – Т. 24, № 1. – С. 9–18.Emelichev V. A., Mychkov V. I. Postoptimal analysis of the vector version of one investment problem. Trudy Instituta matematiki = Proceedings of the Institute of Mathematics, 2016, vol. 24, no. 1, pp. 9–18 (in Russian).Emelichev, V. On a quasistability radius for multicriteria integer linear programming problem of finding extremum solutions / V. Emelichev, Yu. Nikulin // Кибернетика и систем. анализ. – 2019. – Т. 55, № 6. – С. 80–89.Emelichev V., Nikulin, Y. On the quasistability radius for a multicriteria integer linear programming problem of finding extremum solutions. Cybernetics and Systems Analysis, 2019, vol. 55, no. 6, pp. 949–957. https://doi.org/10.1007/s10559-019-00205-9Emelichev, V. Post-optimal analysis for multicriteria integer linear programming problem with parametric optimality / V. Emelichev, Yu. Nikulin // Control and Cybernetics. – 2020. – Vol. 49, № 2. – P. 163–178.Emelichev V., Nikulin Yu. Post-optimal analysis for multicriteria integer linear programming problem with parametric optimality. Control and Cybernetics, 2020, vol. 49, no. 2, pp. 163–178.Гордеев, Э. Н. Сравнение трех подходов к исследованию устойчивости решений задач дискретной оптимизации и вычислительной геометрии / Э. Н. Гордеев // Дискрет. анализ и исслед. операций. – 2015. – Т. 22, вып. 3. – С. 18–35.Gordeev E. N. 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, no. 3, pp. 358–366. https://doi.org/10.1134/S1990478915030072Бухтояров, С. Е. Аспекты устойчивости многокритериальной задачи целочисленного линейного программирования / С. Е. Бухтояров, В. А. Емеличев // Дискрет. анализ и исслед. операций. – 2019. – Т. 26, № 1. – С. 5–19. https://doi.org/10.33048/daio.2019.26.624Bukhtoyarov S. E., Emelichev V. A. Stability aspects of multicriteria integer linear programming problems. Journal of Applied and Industrial Mathematics, 2019, vol. 13, no. 1, pp. 22–29. https://doi.org/10.1134/S1990478919010034Emelichev, V. A. Stability measures for multicriteria quadratic Boolean programming problem of finding extremum solutions / V. A. Emelichev, Y. V. Nikulin // Тр. Ин-та математики. – 2017. – Т. 25, № 2. – С. 82–90.Emelichev V. A., Nikulin Yu. V. Stability measures for multicriteria quadratic Boolean programming problem of finding extremum solutions. Trudy Instituta matematiki = Proceedings of the Institute of Mathematics, 2017, vol. 25, no. 2, pp. 82–90 (in Russian).Scheduling under uncertainty. Theory and algorithms / Y. Sotskov [et al.]. – Minsk: Belaruskaya nauka, 2010. – 328 p.Sotskov Y., Sotskova N., Lai T., Werner F. Scheduling under Uncertainty. Theory and Algorithms. Minsk, Belaruskaya nauka Publ., 2010. 328 p.Nikulin, Y. Accuracy and stability functions for a problem of minimization a linear form on a set of substitutions / Y. Nikulin // Sequencing and Scheduling with Inaccurate Data / eds.: Y. Sotskov, F. Werner. – Nova Science Pub Inc., 2014. – Ch. 15. – P. 409–426.Nikulin Y. Accuracy and stability functions for a problem of minimization a linear form on a set of substitutions. Sotskov Y., Werner F. (eds.). Sequencing and Scheduling with Inaccurate Data. Ch. 15. Nova Science Pub Inc., 2014, pp. 409–426.Емеличев, В. А. О количественной мере устойчивости векторной задачи целочисленного программирования / В. А. Емеличев, Д. П. Подкопаев, // Журн. вычисл. математики и мат. физики. – 1998. – Т. 38, № 11. – С. 1801–1805.Emelichev V. A., Podkopaev D. P. On a quantitative measure of stability for a vector problem in integer programming. Computational Mathematics and Mathematical Physics, 1998, vol. 38, no. 11, pp. 1727–1731.Stability and regularization of vector problem of integer linear programming / V. Emelichev [et al.] // Optimization. – 2002. – Vol. 51, № 4. – P. 645–676. https://doi.org/10.1080/0233193021000030760Emelichev V. A., Girlich E., Nikulin Yu. V., Podkopaev D. P. Stability and regularization of vector problem of integer linear programming. Optimization, 2002, vol. 51, no. 4, pp. 645–676. https://doi.org/10.1080/0233193021000030760Емеличев, В. А. О радиусе устойчивости векторной задачи целочисленного линейного программирования в случае регулярности нормы в критериальном пространстве / В. А. Емеличев, К. Г. Кузьмин // Кибернетика и систем. анализ. – 2010. – Т. 46, № 1. – С. 82–89.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, 2010, vol. 46, no. 1, pp. 72–79. https://doi.org/10.1007/s10559010-9185-2Emelichev, V. A. Estimates of stability radius of multicriteria Boolean problem with Hölder metrics in parameter spaces / V. A. Emelichev, K. G. Kuzmin, V. I. Mychkov // Bull. Acad. Sci. Moldova. Math. – 2015. – № 2 (78). – P. 74–81.Emelichev V. A., Kuzmin K. G., Mychkov V. I. Estimates of stability radius of multicriteria Boolean problem with Hölder metrics in parameter spaces. Bulletin of the Academy of Sciences of Moldova. Mathematics, 2015, no. 2 (78), pp. 74–81.Emelichev, V. Post-optimal analysis for multicriteria integer linear programming problem of finding extremum solutions / V. Emelichev, Yu. Nikulin // Control and Cybernetics. – 2018. – Vol. 47, № 3. – P. 225–238.Emelichev V., Nikulin Yu. Post-optimal analysis for multicriteria integer linear programming problem of finding extremum solutions. Control and Cybernetics, 2018, vol. 47, no. 3, pp. 225–238.Emelichev, V. A. On two stability types for a multicriteria integer linear programming problem / V. A. Emelichev, S. E. Bukhtoyarov // Bull. Acad. Sci. Moldova. Math. –2020. – Vol. 92, № 1. – P. 17–30.Emelichev V. A., Bukhtoyarov S. E. On two stability types for a multicriteria integer linear programming problem. Bulletin of the Academy of Sciences of Moldova. Mathematics, 2020, vol. 92, no. 1, pp. 17–30.Emelichev, V. On one type of stability for multiobjective integer linear programming problem with parameterized optimality / V. Emelichev, Yu. Nikulin // Comput. Sci. J. Moldova. – 2020. – Vol. 28, № 3. – P. 249–268.Emelichev V., Nikulin Yu. On one type of stability for multiobjective integer linear programming problem with parameterized optimality. Computer Science Journal of Moldova, 2020, vol. 28, no. 3, pp. 249–268.Подиновский, В. В. Парето-оптимальные решения многокритериальных задач / В. В. Подиновский, В. Д. Ногин. – М.: Наука, 1982. – 256 с.Podinovskii V. V., Nogin V. D. Pareto-Optimal Solutions of Multicriteria Problems. Moscow, Nauka Publ., 1982. 256 p. (in Russian).Леонтьев, В. К. Устойчивость в линейных дискретных задачах / В. К. Леонтьев // Проблемы кибернетики. – 1979. – Вып. 35. – С. 169–184.Leont'ev V. K. Stability in linear discrete problems. Problemy kibernetiki [Problems of Cybernetics], 1979, no. 35, pp. 169–184 (in Russian).

The authors declare that there are no conflicts of interest present.