On necessary and sufficient conditions for stability and quasistability in combinatorial multicriteria optimization

• Autorzy: Kuzmin K. G. , Nikulin Y. V. , Makela M. M.
• Języki publikacji: EN

Abstrakty

EN

We consider a multiple objective combinatorial optimization problem with an arbitrary vector-criterion. The necessary and sufficient conditions for stability and quasistability are obtained for large classes of problems with partial criteria possessing certain properties of regularity.

Słowa kluczowe

EN

sensitivity analysis; multiple criteria; combinatorial optimization; Pareto set; stability conditions

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2017
• Tom: Vol. 46, no. 4
• Strony: 361--382
• Opis fizyczny: Bibliogr. 30 poz., rys.

Twórcy

autor

Kuzmin K. G.

• Department of Computer Science, Georgia State University, 1 Park Place, Atlanta, GA 30303, USA

autor

Nikulin Y. V.

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

autor

Makela M. M.

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

Bibliografia

• [1] EHRGOTT, M. (2000) Multicriteria Optimization. Springer, Berlin.
• [2] 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.
• [3] EMELICHEV, V., GUREVSKY, E. and KUZMIN, K. (2010) On stability of some lexicographic integer problem. Control and Cybernetics 39 (3), 811–826.
• [4] EMELICHEV, V., KARELKINA, O. and KUZMIN, K. (2012) Qualitative stability analysis of multicriteria combinatorial minimin problems. Control and Cybernetics 41 (1), 57–79.
• [5] EMELICHEV, V., KOTOV, V., KUZMIN, K., LEBEDEVA, T., SEMENOVA N. and SERGIENKO T. (2012) Stability and effective algorithms for solving multiobjective discrete optimization problems with incomplete information. Journal of Automation and Information Sciences 26 (2), 27–41.
• [6] EMELICHEV, V. and KUZMIN, K. (2006) Stability radius of an efficient solution of a vector problem of integer linear programming in the Golder metric Cybernetics and Systems Analysis 42 (4), 609–614.
• [7] EMELICHEV, V. and KUZMIN, K. (2007) On a type of stability of a multicriteria integer linear programming problem in the case of a monotone norm. Journal of Computer and Systems Sciences International 46 (5), 714–720.
• [8] EMELICHEV V. and KUZMIN, K. (2008) Stability criteria in vector combinatorial bottleneck problems in terms of binary relations. Cybernetics and Systems Analysis 44 (3), 397–404.
• [9] EMELICHEV, V., KUZMIN, K. and NIKULIN, Y. (2005) Stability analysis of the Pareto optimal solution for some vector Boolean optimization problem. Optimization 54 (6), 545–561.
• [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] 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.
• [12] GORSKI, J. and RUZIKA, S. (2009) On k-max optimization. Operations Research Letters 37 (1), 23–26.
• [13] GORSKI, J., KLAMROTH, K. and RUZIKA, S. (2012) Generalized multiple objective bottleneck problems. Operations Research Letters 40(4), 276–281.
• [14] GREENBERG, H. (1998) An annotated bibliography for post-solution analysis in mixed integer and combinatorial optimization. In: Woodruff, D. (Ed.), Advances in Computational and Stochastic Optimization, Logic Programming and Heuristic Search. Kluwer Academic Publishers, 97–148.
• [15] GUREVSKY E., BATTA¨IA, O. and DOLGUI, A. (2012) Balancing of simple assembly lines under variations of task processing times. Annals of Operations Research 201 (1), 265–286.
• [16] KASPERSKI, A. (2008) Discrete Optimization with Interval Data, Minmax Regret and Fuzzy Approach. Springer, Berlin.
• [17] KOUVELIS, P. and YU, G. (1997) Robust Discrete Optimization and its Applications. Kluwer, Norwell.
• [18] 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.
• [19] LAI, T., SOTSKOV, Y., SOTSKOVA, N. and WERNER, F. (2004) Mean flow time minimization with given bounds on processing times. European Journal of Operational Research 159 (3), 558–573.
• [20] LIBURA, M. and NIKULIN, Y. (2004) Stability and accuracy functions in multicriteria combinatorial optimization problem with Σ-minmax and Σ-minmin partial criteria. Control and Cybernetics 33 (3), 511–524.
• [21] LIBURA, M. and NIKULIN, Y. (2006) Stability and accuracy functions in multicriteria linear combinatorial optimization problems. Annals of Operations Research 147, 255–267.
• [22] MIETTINEN, K. (1999) Nonlinear Multiobjective Optimization. Kluwer, Boston.
• [23] NIKULIN, Y. (2014) Accuracy and stability functions for a problem of minimization of a linear form on a set of substitutions. In: Y. Sotskov and F. Werner, eds., Sequencing and Scheduling with Inaccurate Data. Nova, New York.
• [24] NIKULIN, Y., KARELKINA, O. and MAKELA, M. (2013) On accuracy, robustness and tolerances in vector Boolean optimization. European Journal of Operational Research 224 (3), 449–457.
• [25] NOGIN, V. (2018) Reduction of the Pareto Set. Springer, Cham.
• [26] SOTSKOV, Y., ALLAHVERDI, A. and LAI, T. (2004) Flowshop scheduling problem to minimize total completion time with random and bounded processing times. Journal of the Operational Research Society 55 (3), 277–286.
• [27] SOTSKOV, Y., EGOROVA, N. and LAI, T. (2009) Minimizing total weighted flow time of a set of jobs with interval processing times. Mathematical and Computer Modelling 50 (3–4), 556–573.
• [28] SOTSKOV, Y. and LAI, T. (2012) Minimizing total weighted flow under uncertainty using dominance and a stability box. Computers and Operations Research 39 (6), 1271–1289.
• [29] SOTSKOV, Y., SOTSKOVA, N., LAI, T. and WERNER, F. (2010) Scheduling under Uncertainty, Theory and Algorithms, Belorusskaya nauka, Minsk.
• [30] SOTSKOV, Y., TANAEV, V. and WERNER, F. (1998) Stability radius of an optimal schedule: a survey and recent developments. Industrial Applications of Combinatorial Optimization 16, 72–108.

Uwagi

PL

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