Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Archive
Cybernetics And Systems Analysis
International Theoretical Science Journal
-->

UDC 519.85
L.N. Koliechkina1, О.A. Dvirna2, S.V. Khovben3


1 University of Lodz, Lodz,
Poland

lkoliechkina@gmail.com

2 Poltava University of Economics and Trade,
Poltava, Ukraine

lenadvirna@gmail.com

3 Poltava University of Economics and Trade,
Poltava, Ukraine

hovben1996@gmail.com

TWO-STEP SOLUTION METHOD FOR VECTOR OPTIMIZATION
PROBLEMS ON PERMUTATION CONFIGURATION

Abstract. A class of problems of vector Euclidean combinatorial optimization is considered as problems of discrete optimization on the set of combinatorial configurations mapped into the Euclidean space. The properties of the graphs of combinatorial configurations are given, which are used to describe the new method. A two-stage method for solving problems of vector Euclidean combinatorial optimization on combinatorial configurations of permutations is proposed. The results of a numerical experiment and their analysis are presented.

Keywords: vector problem, multiobjective optimization, combinatorial configuration, Euclidean combinatorial sets, vector criterion, Euclidean models.



FULL TEXT

REFERENCES

  1. Jahn J. Vector optimization: theory, applications and extensions. Berlin; Heidelberg: Springer-Verlag, 2004. 400 p.

  2. Emelichev V., Kuzmin K., Nikulin Y. Stability analysis of the Pareto optimal solutions for some vector boolean optimization problem. Optimization. 2005. Vol. 54, N 6. P. 545–561.

  3. Engau A., Sigler D. Pareto solutions in multicriteria optimization under uncertainty. European Journal of Operational Research. 2020. Vol. 281, N 2. P. 357–368.

  4. Ehrgott M., Wiecek M. Mutiobjective programming. Multiple Criteria Decision Analysis: State of the Art Surveys. Figueira J., Greco S., Ehrgott M. (Eds). New York: Springer, 2005. P. 667–708.

  5. Podinovski V.V. Decision making under uncertainty with unknown utility function and rank-ordered probabilities. European Journal of Operational Research. 2014. Vol. 239, N 2. P. 537–541.

  6. Kuzmin K., Nikulin Y., Mkel M. On necessary and sufficient conditions of stability and quasistability in combinatorial multicriteria optimization. Control and Cybernetics. 2017. Vol. 46, N 4. P. 361–382.

  7. Emelichev V., Nikulin Yu. On a quasistability radius for multicriteria integer linear programming problem of finding extremum solutions. Cybernetics and Systems Analysis. 2019. Vol. 55, N 6. P. 949–957. https://doi.org/10.1007/s10559-019-00205-9.

  8. Sergienko I.V., Perepelitsa V.A. Polynomial and NP-complete multicriteria problems of listing alternatives. Theory and Software Implementation of Discrete Optimization Methods. Kiev: V.M. Glushkov Institute of Cybernetics, 1989. P. 58–69.

  9. Studniarski M., Koliechkina K., Dvernaya E. Solving a combinatorial multiobjective optimization problem by genetic algorithm. Contemporary Computational Science. Kulczycki P., Kowalski P., ukasik Sz. (Eds). Proc. 3rd Conference on Information Technology, Systems Research and Computational Physics, Contemporary Computational Science (2–5 July 2018, Cracow, Poland). Cracow, 2018, P. 188–200.

  10. Petrov E.G., Kryuchkovsky V.V., Petrov K.E. Normative formalization of the decision-making process in conditions of multi-criteria and interval uncertainty. Problemy informatsiynykh tekhnolohiy. 2014. N 1. P. 7–13.

  11. Sergienko I.V., Shilo V.P. Modern approaches to solving complex discrete optimization problems. Journal of Automation and Information Sciences. 2016. Vol. 48, N 1. P. 15–24.

  12. Semenova NV, Kolechkina LM Vector problems of discrete optimization on combinatorial sets: research methods and solutions [in Ukrainian]. Kyiv: Nauk. Dumka, 2009. 266 p.

  13. Koliechkina L.N., Pichugina O. Multiobjective optimization on permutations with applications. DEStech Transactions on Computer Science and Engineering. 2018. P. 61–75. https://doi.org/ 10.12783/dtcse/optim2018/27922.

  14. Koliechkina L., Pichugina O., Yakovlev S. A Graph-theoretic approach to multiobjective permutation-based optimization. In: Optimization and Applications. Jacimovic M., Khachay M., Malkova V., Posypkin M. (Eds.). Proc. 10th International Conference (OPTIMA 2019) (30 September–4 October, 2019, Petrovac, Montenegro). Cham: Springer International Publishing, 2020. P. 383–400.

  15. Semenova N.V., Kolechkina L.N., Nagornaya A.N. Solution and investigation of vector problems of combinatorial optimization on a set of permutations. Journal of Automation and Information Sciences. 2008. Vol. 40, N 12. P. 67–80.

  16. Semenova N.V., Kolechkina L.N. A polyhedral approach to solving multicriterion combinatorial optimization problems over sets of polyarrangements. Cybernetics and Systems Analysis. 2009. Vol. 45, N 3. P. 438–445. https://doi.org/10.1007/s10559-009-9110-8.

  17. Semenova N.V., Kolechkina L.N., Nagornaya A.N. On approach to solving vector problems with fractionally linear functions of the criteria on the combinatorial set of arrangements. Journal of Automation and Information Sciences. 2010. Vol. 42, N 2. P. 67–80.

  18. Koliechkina L., Dvirna O.A., Nahirna A.N. Construction of a mathematical model of multiobjective optimization on permutations. Control Systems and Computers. 2020. N 2 (286). P. 23–29.

  19. Stoyan Y.G., Yakovlev S.V. Theory and methods of Euclidian combinatorial optimization: current status and prospects. Cybernetics and Systems Analysis. 2020. Vol. 56, N 3. P. 366–379. https://doi.org/10.1007/s10559-020-00253-6.

  20. Stoyan Y.G., Yakovlev S.V., Pichugina O.S. The Euclidean combinatorial configurations. Kharkiv: Constanta, 2017. 268 p.

  21. Yakovlev S.V. Formalization of spatial configuration optimization problems with a special function class. Cybernetics and Systems Analysis. 2019. Vol. 55, N 4. P. 581–589. https://doi.org/10.1007/ s10559-019-00167-y.

  22. Korte B., Vygen J. Combinatorial optimization: theory and algorithms. Berlin; Heidelberg: Springer-Verlag, 2018. 698 p.

  23. Pardalos P.M., Du D-Z., Graham R.L. Handbook of combinatorial optimization. New York: Springer-Verlag, 2013. 3409 p.

  24. Papadimitriou C.H., Steiglitz K. Combinatorial optimization: algorithms and complexity. Mineola (NY): Dover Publications, 2013. 528 p.

  25. Butenko S., Pardalos P.M., Shylo V. Optimization methods and applications: in honor of Ivan V. Sergienko’s 80th birthday. New York: Springer International Publishing, 2017. 639 p. https:// doi.org/10.1007/978-3-319-68640-0.

  26. Hulianytskyi L., Riasna I. Formalization and classification of combinatorial optimization problems. In: Optimization Methods and Applications. Butenko S., Pardalos P.M., Shylo V. (Eds.). New York: Springer International Publishing, 2017. P. 239–250.

  27. Donets G.P., Kolechkina L.M. Extreme problems on combinatorial configurations [in Ukrainian]. Poltava: RVV PUET, 2011. 309 p.

  28. Koliechkina L., Pichugina O. A horizontal method of localizing values of a linear function in permutation-based optimization. In: Optimization of Complex Systems: Theory, Models, Algorithms and Applications. Le Thi H.A., Le H.M., Pham Dinh T. (Eds.). Cham: Springer International Publishing, 2020. P. 355–364.

  29. Koliechkina L.N., Dvernaya O.A., Nagornaya A.N. Modified coordinate method to solve multicriteria optimization problems on combinatorial configurations. Cybernetics and Systems Analysis. 2014. Vol. 50, N 4. P. 620–626. https://doi.org/10.1007/s10559-014-9650-4.

  30. Yakovlev S., Pichugina O., Koliechkina L. A lower bound for optimization of arbitrary function on permutations. Lecture Notes in Computational Intelligence and Decision Making. Proc. International Scientific Conference “Intellectual Systems of Decision Making and Problem of Computational Intelligence” (ISDMCI 2020) (25–29 May, 2020, Zalizniy Port, Ukraine). Zalizniy Port, 2020. P. 195–212.

  31. Donets G.P., Koliechkina L.N., Nahirna A.N. A method to solve conditional optimization problems with quadratic objective functions on the set of permutations. Cybernetics and Systems Analysis. 2020. Vol. 56, N 2. P. 278-288. https://doi.org/10.1007/s10559-020-00243-8.

  32. Koliechkina L.N., Nahirna A.N. Solutions of the combinatorial problem with a quadratic fractional objective function on the set of permutations. Cybernetics and Systems Analysis. 2020. Vol. 56, N 3. P. 455–465. https://doi.org/10.1007/s10559-020-00261-6.

  33. Koliechkina L.N., Dvirna O.A. Solving extremum problems with linear fractional objective functions on the combinatorial configuration of permutations under multicriteriality. Cybernetics and Systems Analysis. 2017. Vol. 53, N 4. P. 590–599. https://doi.org/10.1007/s10559-017-9961-3.

  34. Koliechkina L.N., Nagornaya A.N., Semenov V.V. Method of solving problem of conditional optimization on combinatorial set of arrangements. Journal of Automation and Information Sciences. 2019. Vol. 51, N 8. P. 31–42.

  35. Yemelichev V.A., Kovalev M.M., Kravtsov M.K. Polytopes, graphs and optimization. Cambridge: Cambridge University Press, 1984. 243 p.




© 2021 Kibernetika.org. All rights reserved.