Post-optimal analysis for multicriteria integer linear programming problem of finding extreme solutions

• Autorzy: Emelichev V. A. , Nikulin Y.
• Języki publikacji: EN

Abstrakty

EN

We consider a multicriteria problem of integer linear programming and study the set of all individual criterion minimizers (extreme solutions) playing an important role in determining the range of Pareto optimal set. In this work, the lower and upper attainable bounds on the stability radius of the set of extreme solutions are obtained in the situation where solution and criterion spaces are endowed with various H¨older’s norms. In addition, the case of the Boolean problem is analyzed. Some computational challenges are also discussed.

Słowa kluczowe

EN

sensitivity analysis; multiple criteria; extreme solutions; stability radius; integer linear programming

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2018
• Tom: Vol. 47, no. 3
• Strony: 225--238
• Opis fizyczny: Bibliogr. 38 poz.

Twórcy

autor

Emelichev V. A.

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

autor

Nikulin Y.

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

Bibliografia

• [1] BRANKE, J., DEB, K., MIETTINEN, K., SLOWINSKI R. (eds.) (2007) Practical Approaches to Multi-Objective Optimization. Dagstuhl seminar proceedings 06501. Internationales Begegnungs- und Forschungszentrum (IBFI), Schloss Dagstuhl, Germany.
• [2] BUKHTOYAROV, S. and EMELICHEV, V. (2015) On the stability measure of solutions to a vector version of an investment problem. Journal of Applied and Industrial Mathematics, 9 (3), 328–334.
• [3] CHAKAVARTI, N. and WAGELMANS, A. (1999) Calculation of stability radius for combinatorial optimization problems. Oper. Res. Lett., 23, 1–7.
• [4] EMELICHEV, V. and PODKOPAEV, D. (1998) On a quantitative measure of stability for a vector problem in integer programming. Journal of Computatonal Physics and Mathematics, 38 (11), 1727–1731.
• [5] EMELICHEV, V. and PODKOPAEV, D. (2001) Stability and regularization of vector problems of integer linear programming. Diskretnyi Analiz i Issledovanie Operatsii. Ser. 2, 8 (1), 47–69.
• [6] EMELICHEV, V., GIRLICH, E., NIKULIN, Y. and PODKOPAEV, D. (2002) Stability and regularization of vector problems of integer linear programming. Optimization, 51 (4), 645–676.
• [7] EMELICHEV, V., KRICHKO, V. and NIKULIN, Y. (2004) The stability radius of an efficient solution in minimax Boolean programming problem. Control and Cybernetics, 33 (1), 127–132.
• [8] EMELICHEV, V. and KUZMIN, K. (2007) 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, 46 (5), 714–720.
• [9] EMELICHEV, V. and KUZMIN, K. (2010) Stability radius of a vector integer linear programming problem: case of a regular norm in the space of criteria. Cybernetics and Systems Analysis, 46 (1), 72–79.
• [10] EMELICHEV, V. and PODKOPAEV, D. (2010) Quantitative stability analysis for vector problems of 0-1 programming. Discrete Optimization, 7 (1-2), 48–63.
• [11] EMELICHEV, V, KARELKINA, O. and KUZMIN, K. (2012) Qualitative stability analysis of combinatorial minmin problems. Control and Cybernetics, 41 (1), 57–79.
• [12] 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.
• [13] EMELICHEV, V., KOTOV, V., KUZMIN, K., LEBEDEVA, T., SEMENOVA, N. and SERGIENKO, T. (2014) Stability and effective algorithms for solving multiobjective discrete optimization problems with incomplete information. Journal of Automation and Information Sciences, 46 (2), 27–41.
• [14] EMELICHEV, V. and NIKULIN, Y. (2018) Aspects of stability for multicriteria quadratic problems of Boolean programming, Bul. Acad. Stiinte Repub. Mold. Mat., 87 (2), 30–40.
• [15] EHRGOTT, M. (2005) Multicriteria Optimization. Springer, Birkh¨auser.
• [16] GORDEEV, E. (2015) Comparison of three approaches to studying stability of solutions to problems of discrete optimization and computational geometry. Journal of Applied and Industrial Mathematics, 9 (3), 358–366.
• [17] HADAMARD, J. (1923) Lectures on Cauchys Problem in Linear Partial Differential Equations. Yale University Press, Yale.
• [18] HARDY, G., LITTLEWOOD, J. and POLYA, G. (1988) Inequalities. Cambridge University Press, Cambridge.
• [19] 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.
• [20] KUZMIN, K., NIKULIN, Y. and M¨AKEL¨A, M. (2017) On necessary and suf ficient conditions of stability and quasistability in combinatorial multicriteria optimization. Control and Cybernetics, 46 (4), 361–382.
• [21] LEBEDEVA, T. and SERGIENKO, T. (2008) Different types of stability of vector integer optimization problem: general approach. Cybernetics and Systems Analysis, 44 (3), 429–433.
• [22] LEBEDEVA, T., SEMENOVA, N. and SERGIENKO, T. (2014a) Qualitative characteristics of the stability of vector discrete optimization problems with different optimality principles. Cybernetics and Systems Analysis, 50 (2), 228–233.
• [23] LEBEDEVA, T., SEMENOVA, N. and SERGIENKO, T. (2014b) Properties of perturbed cones ordering the set of feasible solutions of vector optimization problem. Cybernetics and Systems Analysis, 50 (5), 712–717.
• [24] LEONTEV, V. (2007) Discrete Optimization. Journal of Computatonal Physics and Mathematics, 47 (2), 328–340.
• [25] LIBURA M., VAN DER POORT E.S., SIERKSMA G., VAN DER VEEN J.A.A. (1998) Stability aspects of the traveling salesman problem based on k-best solutions. Discrete Applied Mathematics; 87:159–185.
• [26] LIBURA, M. and NIKULIN, Y. (2006) Stability and accuracy functions in multicriteria linear combinatorial optimization problem. Annals of Operations Research, 147 (1), 255–267.
• [27] LOTOV, A. and POSPELOV, I. (2008) Multicriteria Decision Making Problems, Fizmatlit, Moscow.
• [28] MIETTINEN, K. (1999) Nonlinear Multiobjective Optimization. Kluwer Academic Publishers, Boston.
• [29] 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.
• [30] NIKULIN, Y., KARELKINA, O. and M¨AKEL¨A, M. (2013) On accuracy, robustness and tolerances in vector Boolean optimization. European Journal of Operational Research, 224, 449–457.
• [31] NIKULIN, Y. (2014) Accuracy and stability functions for a problem of minimization a linear form on a set of substitutions. Chapter in: Sequencing and Scheduling with Inaccurate Data, Y. Sotskov and F. Werner eds., Nova Science Pub. Inc.
• [32] NOGHIN, V. (2018) Reduction of the Pareto Set: An Axiomatic Approach (Studies in Systems, Decision and Control). Springer, Cham.
• [33] PARETO, V. (1909) Manuel D’´Economie Politique. Qiard, Paris.
• [34] PODINOVSKII, V. and NOGHIN, V. (1982) Pareto-Optimal Solutions of Multicriteria Problems. Fizmatlit, Moscow.
• [35] ROLAND, J., SMET, Y. and FIGUEIRA, J. (2012) On the calculation of stability radius for multi-objective combinatorial optimization problems by inverse optimization. 4OR-Q. J. Oper. Res., 10, 379–389.
• [36] SERGIENKO, I. and SHILO, I. (2003) Discrete Optimization Problems. Problems, Methods, Research. Naukova dumka, Kiev.
• [37] SOTSKOV, Y., SOTSKOVA, N., LAI, T. and WERNER, F. (2010) Scheduling under Uncertainty, Theory and Algorithms. Belaruskaya nauka, Minsk.
• [38] STEUER, R. (1986) Multiple Criteria Optimization: Theory, Computation and Application. John Wiley&Sons, New York.

Uwagi

PL

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).