Stability measure of multicriteria integer linear programming problem with a parametric optimality principle

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.

1. Hadamard J. Lectures on Cauchy’s Problem in Linear Partial Differential Equations. Yale, Yale University Press, 1923. 338 p.

2. 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).

3. Sergienko I. V., Shilo V. P. Discrete Optimization Problems. Problems, Methods, Research. Kiev, Naukova dumka Publ., 2003. 261 p. (in Russian).

4. 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

5. 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-9

6. 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.

7. 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

8. 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

9. 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).

10. 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-9

11. 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.

12. 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

13. Bukhtoyarov 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/S1990478919010034

14. 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).

15. Sotskov Y., Sotskova N., Lai T., Werner F. Scheduling under Uncertainty. Theory and Algorithms. Minsk, Belaruskaya nauka Publ., 2010. 328 p.

16. 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.

17. 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.

18. Emelichev 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

19. 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-2

20. 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.

21. 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.

22. 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.

23. 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.

24. Podinovskii V. V., Nogin V. D. Pareto-Optimal Solutions of Multicriteria Problems. Moscow, Nauka Publ., 1982. 256 p. (in Russian).

25. Leont'ev V. K. Stability in linear discrete problems. Problemy kibernetiki [Problems of Cybernetics], 1979, no. 35, pp. 169–184 (in Russian).