Volume 26, No 1, 2019, P. 5-19

UDC 519.8
S. E. Bukhtoyarov and V. A. Emelichev
Stability aspects of multicriteria integer linear programming problems

Abstract:
Under consideration are the multicriteria integer linear programming problems with finitely many feasible solutions. The problem itself consists in finding a set of extremal solutions. We derive some lower and upper bounds for the $T_1$-stability radius under assumption that arbitrary Hölder norms are given in the solution and criteria spaces. A class of the problems with an infinitely large stability radius is specified. We also consider the case of the multicriteria linear Boolean problem.
Bibliogr. 22.

Keywords: multicriteria ILP problem, set of extremal solutions, stability radius, $T_1$-stability, the Hölder norm.

DOI: 10.33048/daio.2019.26.624

Sergey E. Bukhtoyarov ¹
Vladimir A. Emelichev ¹
1. Belarusian State University,
4 Nezavisimosti Ave., 220030 Minsk, Belarus
e-mail: vemelichev@gmail.com

Received July 15, 2018
Revised October 19, 2018
Accepted November 28, 2018

References

[1] M. A. Aizerman and F. T. Alekserov, The Alternative Choice: Theoretical Foundations, Nauka, Moscow, 1990 [Russian].

[2] S. E. Bukhtoyarov and V. A. Emelichev, On the stability measure of solutions to a vector variant of an investment problem, Diskretn. Anal. Issled. Oper., 22, No. 2, 5–16, 2015 [Russian]. Translated in Appl. Ind. Math., 9, No. 3, 328–334, 2015.

[3] S. E. Bukhtoyarov and V. A. Emelichev, On a stability type of an integer linear programming problem with several criteria, Proc. 8th Int. Conf. “Tanaevskie chteniya”, Minsk, Belarus, Mar. 27–30, 2018, pp. 48–51, OIPI NAN Belarusi, Minsk, 2018 [Russian].

[4] E. N. Gordeev, Comparison of three approaches to studying stability of solutions to problems of discrete optimization and computational geometry, Diskretn. Anal. Issled. Oper., 22, No. 3, 18–35, 2015 [Russian]. Translated in Appl. Ind. Math., 9, No. 3, 358–366, 2015.

[5] V. A. Emelichev and V. V. Korotkov, On stability of a vector Boolean investment problem with Wald’s criteria, Diskretn. Mat., 24, No. 3, 3–16, 2012 [Russian]. Translated in Discrete Math. Appl., 22, No. 4, 367–381, 2012.

[6] V. A. Emelichev, V. M. Kotov, K. G. Kuzmin, T. T. Lebedeva, N. V. Semenova, and T. I. Sergienko, Stability and effective algorithms for solving multiobjective discrete optimization problems with incomplete
information, Probl. Upr. Inform., No. 1, 53–67, 2014 [Russian]. Translated in J. Autom. Inf. Sci., 46, No. 2, 27–41, 2014.

[7] V. A. Emelichev and K. G. Kuzmin, On a type of stability of a milticriteria integer linear programming problem in the case of a monotone norm, Izv. RAN, Teor. Sist. Upravl., No. 5, 45–51, 2007 [Russian]. Translated in J. Comput. Syst. Sci. Int., 46, No. 5, 714–720, 2007.

[8] V. A. Emelichev and K. G. Kuzmin, A general approach to studying the stability of a Pareto optimal solutions of a vector integer linear programming problem, Diskretn. Mat., 19, No. 3, 79–83, 2007 [Russian]. Translated in Discrete Math. Appl., 17, No. 4, 349–354, 2007.

[9] V. A. Emelichev and K. G. Kuzmin, Stability radius of a vector integer linear programming problem: Case of a regular norm in the space of criteria, Kibern. Sist. Anal., No. 1, 82–89, 2010 [Russian]. Translated in Cybern. Syst. Anal., 46, No. 1, 72–79, 2010.

[10] V. A. Emelichev and K. G. Kuzmin, Stability analysis of the effective solution to the vector problem on the maximal cut of a graph, Diskretn. Anal. Issled. Oper., 20, No. 4, 27–35, 2013 [Russian].

[11] V. A. Emelichev and K. G. Kuzmin, On the T1-stability radius of a multicriteria linear Boolean problem with Hölder norms in parameter spaces, Tavricheskiy Vestn. Mat. Inform., 30, No. 1, 49–64, 2016 [Russian].

[12] V. A. Emelichev and D. P. Podkopaev, Stability and regularization of vector integer programs, Diskretn. Anal. Issled. Oper., Ser. 2, 8, No. 1, 47–69, 2001 [Russian].

[13] K. G. Kuzmin, A general approach to the calculation of stability radii for the max-cut problem with multiple criteria, Diskretn. Anal. Issled. Oper., 22, No. 5, 30–51, 2015 [Russian]. Translated in Appl. Ind. Math., 9, No. 4, 527–539, 2015.

[14] V. K. Leontiev, Stability in linear discrete problems, in Problems of Cybernetics, Vol. 35, pp. 169–184, Nauka, Moscow, 1979 [Russian].

[15] A. V. Lotov and I. I. Pospelova, Multicriteria Decision-Making Problems, MAKS Press, Moscow, 2008 [Russian].

[16] V. V. Podinovski and V. D. Nogin, Pareto-Optimal Solutions to Multicriteria Problems, Fizmatlit, Moscow, 2007 [Russian].

[17] I. V. Sergienko and V. P. Shilo, Discrete Optimization Problems: Problems, Solution Methods, Research, Naukova dumka, Kiev, 2003 [Russian].

[18] L. A. Sholomov, Logical Methods for Investigation of Discrete Choice Models, Nauka, Moscow, 1989 [Russian].

[19] D. B. Yudin, Computational Methods in Decision-Making Theory, Nauka, Moscow, 1989 [Russian].

[20] V. A. Emelichev, S. E. Bukhtoyarov and V. I. Mychkov, An investment problem under multicriteriality, uncertainty and risk, Bul. Acad. Stiinte Repub. Mold., Mat., No. 3, 82–98, 2016.

[21] V. A. Emelichev, E. Girlich, Yu. V. Nikulin and D. P. Podkopaev, Stability and regularization of vector problem of integer linear programming, Optimization, 51, No. 4, 645–676, 2002.

[22] V. A. Emelichev and D. P. Podkopaev, Quantitative stability analysis for vector problems of 0–1 programming, Discrete Optim., 7, No. 1–2, 48–63, 2010.