Post-optimal analysis for multicriteria integer linear programming problem with parametric optimality

• Autorzy: Emelichev Vladimir , Nikulin Yury
• Języki publikacji: EN

Abstrakty

EN

This paper addresses a multicriteria problem of integer linear programming with parametric optimality. Parameterizations is introduced by dividing a set of objectives into a family of disjoint subsets, within each Pareto optimality is used to establish dominance between alternatives. The introduction of this principle allows us to connect such classical optimality sets as Pareto and extreme. The parameter space of admissible perturbations in such problem is formed by a set of additive matrices, with arbitrary Hölder’s norms specified in the solution and criterion spaces. The attainable lower and upper bounds for the radii of quasistability are obtained.

Słowa kluczowe

EN

post-optimal analysis; multiple criteria; quasistability radius; integer linear programming; parametric optimality

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2020
• Tom: Vol. 49, No. 2
• Strony: 163--178
• Opis fizyczny: Bibliogr. 27 poz.

Twórcy

autor

Emelichev Vladimir

• Belarusian State University, Faculty of Mechanics and Mathematics, BLR-220030 Minsk, Belarus

autor

Nikulin Yury

• University of Turku, Department of Mathematics and Statistics, FIN-20014 Turku, Finland

Bibliografia

• Ehrgott, M. (2005) Multicriteria Optimization. Springer, Birkhäuser.
• Emelichev, V., Girlich, E., Nikulin, Yu. and Podkopaev, D. (2002) Stability and regularization of vector problem of integer linear programming. Optimization, 51, 4, 645–676.
• Emelichev, V., Gurevsky, E. and Platonov, A. (2009) On stability and quasi-stability radii for a vector combinatorial problem with a parametric optimality principle. Buletinul Academiei de Stiinte a Republicii Moldova. Matematica, 2(60), 55–61.
• Emelichev, V., Kotov, V., Kuzmin, K., Lebedeva, N., Semenova, N. and Sergienko, T. (2014) Stability and effective algorithms for solving multiobjective discrete optimization problems with incomplete information. J. of Automation and Inf. Sciences, 46, 2, 27–41.
• Emelichev, V. and Nikulin, Yu. (2019) On a quasistability radius for multicriteria integer linear programming problem of finding extremum solutions. Cybernetics and System Analysis, 55, 6, 949–957.
• Emelichev, V. and Kuzmin, K. (2013) A general approach to studying the stability of a Pareto optimal solution of a vector integer linear programming problem. Discrete Mathematics and Applications, 17 (4): 349–354.
• Emelichev, V. and Podkopaev, D. (1998) On a quantitive measure of stability for a vector problem in integer programming. Comp. Math. and Math. Physics., 38, 11, 1727–1731.
• Emelichev, V. and Podkopaev, D. (2001) Stability and regularization of vector problems of integer linear programming. Discrete Analysis and Operation Research, Ser. 2, 8, 1, 47–69.
• Emelichev, V. and Podkopaev, D. (2010) Quantitative stability analysis for vector problems of 0-1 programming. Dicrete Optimization, 7, 1-2, 48–63.
• Gordeev, E. and Leontev, V. (1996) A general approach to the study of the stability of solutions in discrete optimization problems. Computational Mathematics and Mathematical Physics, 1, 53–58.
• Hardy, G., Littlewood, J. and Polya, G. (1988) Inequalities. University Press, Cambridge.
• Karelkina O., Nikulin Y. and Mäkelä, M. (2011) An adaptation of NSGA-II to the stability radius calculation for the shortest path problem. TUCS Technical Report 1017.
• Kuzmin, K. (2015) A general approach to the calculation of stability radii for the max-cut problem with multiple criteria. Journal of Applied and Industrial Mathematics, 9 (4), 527–539.
• Lotov, A. and Pospelova, I. (2008) Multi-Criteria Decision Making Problems. Moscow State University, Moscow.
• Miettinen, K. (1999) Nonlinear Multiobjective Optimization. Kluwer Academic Publishers, Boston.
• Montonen, O., Ranta, T. and Mäkelä, M. (2019) Scheduling the Disposal of the Spent Nuclear Fuel with Interactive Multiobjective Optimization. TUCS Technical Reports 1204, TUCS.
• Nikulin, Y., Karelkina, O. and Mäkelä, M. (2013) On accuracy, robustness and tolerances in vector Boolean optimization. European Journal of Operational Research, 224, 449–457.
• Nikulin, Y. (2009) Stability and accuracy functions in a coalition game with bans, linear payoffs and antagonistic strategies. Annals of Operations Research, 172, 25–35.
• Noghin, V. (2018) Reduction of the Pareto Set: An Axiomatic Approach. Springer, Cham.
• Pareto, V. (1909) Manuel D’economie Politique. V. Giard & E. Briere, Paris.
• Sergienko, I. and Shilo, V. (2003) Discrete Optimization Problems. Problems, Methods, Research. Naukova dumka, Kiev.
• Sholomov, L. (1989) Logical methods for investigating discrete models of choice. Nauka, Moscow.
• Smale, S. (1974) Global analysis and economics V: Pareto theory with constraints. J. of Mathematical Economics, 1, 3, 213–221.
• Steuer, R. (1986) Multiple Criteria Optimization: Theory, Computation and Application. John Wiley&Sons, New York.
• Wilppu, O, M¨akel¨a, M. and Nikulin Y. (2017) New two-slope parameterized achievement scalarizing functions for nonlinear multiobjective optimization. In: Operations Research, Engineering, and Cyber Security:
• Trends in Applied Mathematics and Technology, 113, Springer Optimization and Its Applications, 403–422.
• Yudin, D. (1989) Computational Methods in Decision Making Theory. Nauka, Moscow.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).