Two-Stage Approach for Solving the Multi-Objective Optimization Problem on Combinatorial Configurations

Authors: Liudmyla Koliechkina, Olena Dvirna

Abstract:

The statement of the multi-objective optimization problem on combinatorial configurations is formulated, and the approach to its solution is proposed. The problem is of interest as a combinatorial optimization one with many criteria, which is a model of many applied tasks. The approach to solving the multi-objective optimization problem on combinatorial configurations consists of two stages; the first is the reduction of the multi-objective problem to the single criterion based on existing multi-objective optimization methods, the second stage solves the directly replaced single criterion combinatorial optimization problem by the horizontal combinatorial method. This approach provides the optimal solution to the multi-objective optimization problem on combinatorial configurations, taking into account additional restrictions for a finite number of steps.

Keywords: Discrete set, linear combinatorial optimization, multi-objective optimization, multipermutation, Pareto solutions, partial permutation set, permutation, structural graph.

References:

[1] Ehrgott M. Multicriteria optimization. Berlin; New York: Springer. 2005. P.323
[2] Ehrgott M., Gandibleux X. Multiobjective combinatorial optimization – theory, methodology, and applications. In: Ehrgott, M. and Gandibleux, X. (eds.) Multiple criteria optimization: state of the art annotated bibliographic surveys. Berlin; Springer US, 2003. p. 369–444. https://doi.org/10.1007/0-306-48107-3_8.
[3] Ehrgott M., Wiecek M. Mutiobjective programming. In Multiple Criteria Decision Analysis: State of the Art Surveys, number 78 in International Series in Operations Research & Management Science, Springer New York, 2005. P. 667–708.
[4] Studniarski M., Koliechkina K., Dvernaya E., Solving a Combinatorial Multiobjective Optimization Problem by Genetic Algorithm. In.: Kulczycki P., Kowalski P., Łukasik Sz.(eds). Contemporary Computational Science. 3rd Conference on Information Technology, Systems Research and Computational Physics, Contemporary Computational Science, 2018, P.188-200.
[5] Semenova N.V., Kolechkin L.M. Vector Discrete Optimization Problems on Combinatorial Configurations: Research and Solution Methods (in Ukrainian). Kyiv: Nauk. Dumka, 2009. 266 p.
[6] Koliechkina, L., Pichugina, O.: Multiobjective Optimization on Permutations with Applications. DEStech Transactions on Computer Science and Engineering. 2018. P. 61–75.
[7] Koliechkina, L., Pichugina, O., Yakovlev, S.: A Graph-Theoretic Approach to Multiobjective Permutation-Based Optimization. In: Ja´cimovi´c, M., Khachay, M., Malkova, V., and Posypkin, M. (eds.) Optimization and Applications. Springer International Publishing, Cham 2020. , P. 383–400.
[8] 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. 40, N 12. P. 67–80.
[9] Houda Abadlia, Nadia Smairi, Khaled Ghedira An Enhanced Particle Swarm Optimization Algorithm for Multiobjective Problems. World Academy of Science, Engineering and Technology International Journal of Computer and Information Engineering Vol:12, No:11, 2018
[10] Colbourn C.J., Dinitz J.H. Handbook of Combinatorial Designs, second edition. CRC Press, 2010. 784 p.
[11] Stoyan, Y.G., Yakovlev, S.V., Pichugina, O.S.: The Euclidean combinatorial configurations: a monograph. Constanta, Kharkiv. 2017, 268p.
[12] Stoyan, Y.G., Yakovlev, S.V. Theory and Methods of Euclidian Combinatorial Optimization: Current Status and Prospects. Cybernetics and Systems Analysis. 2020. 56, N 3. P. 366–379.
[13] Korte B., Vygen J. Combinatorial optimization: theory and algorithms. Heidelberg; New York: Springer, 2018. 698 p.
[14] Pardalos P.M., Du D-Z., Graham R.L. Handbook of combinatorial optimization. New York: Springer, 2013. 3409 p.
[15] Papadimitriou C.H., Steiglitz K. Combinatorial optimization: algorithms and complexity. Mineola: Dover Publications, 2013. 528 p.
[16] Sergienko I.V., Shilo V.P. Modern approaches to solving complex discrete optimization problems. Journal of Automation and Information Sciences. 2016. 48, N 1. P. 15–24.
[17] Hulianytskyi L., Riasna I. Formalization and classification of combinatorial optimization problems. Optimization methods and applications. S. Butenko et al. (eds.). New York: Springer, 2017. P. 239–250.
[18] Koliechkina L., Pichugina O. A Horizontal Method of Localizing Values of a Linear Function in Permutation-Based Optimization. In: Le Thi, H.A., Le, H.M., and Pham Dinh, T. (eds.) Optimization of Complex Systems: Theory, Models, Algorithms and Applications. Springer, Cham. 2019. P. 355–364.
[19] Koliechkina L. N., Dvirna O.A., Nagornaya A.N. Modified coordinate method to solve multicriteria optimization problems on combinatorial configurations. Cybernetics and Systems Analysis. 2014. 59, N 4. P. 620–626.
[20] Pichugina O.: Placement problems in chip design: Modeling and optimization. In: 2017 4th International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S T). P. 465–473 (2017).
[21] Yakovlev S. Convex extensions in combinatorial optimization and their applications. Optimization Methods and Applications. 2017. 130. P. 567–584.
[22] Yemelichev V.A., Koval¨ev M.M., Kravtsov M.K. Polytopes, graphs and optimisation. Cambridge University Press, Cambridge. 1984. 243p.
[23] 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.
[24] 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.
[25] Yakovlev S.V., Pichugina O.S. Properties of combinatorial optimization problems over polyhedral-spherical sets. Cybernetics and Systems Analysis. 2018. 54, N 1. P. 99–109.
[26] Pichugina O., Yakovlev S. Optimization on polyhedral-spherical sets: theory and applications. In 2017 IEEE First Ukraine Conference on Electrical and Computer Engeneering (UKRCON 2017). Proceedings. Kyiv, 2017. P. 1167–1175.
[27] Stoyan Yu.G., Sokolovskii V.Z., Yakovlev S.V. Method of balancing rotating discretely distributed masses. Energomashinostroenie. 1982. N 2. P. 4–5.
[28] Yakovlev S.V., Grebennik I.V. Localization of solutions of some problems of nonlinear integer optimization. Cybernetics and Systems Analysis. 1993. 29, N 5. P. 419–426.
[29] Semenova N.V., Kolechkina L.N., Nagirna A.N. An approach to solving discrete vector optimization problems over a combinatorial set of permutations. Cybernetics and Systems Analysis. 2008. 44, N 3. P. 441–451.
[30] Semenova N.V., Kolechkina L.N. A polyhedral approach to solving multicriterion combinatorial optimization problems over sets of polyarrangements. Cybernetics and Systems Analysis. 2009. 45, N 3. P. 438–445.
[31] 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. 42, N 2. P. 67–80.
[32] 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. 53, N 4. P. 590–599.
[33] 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. 51, N.8. P. 31-42.
[34] Donetsk G.P., Kolechkin L.M. Extreme problems on combinatorial configurations (in Ukrainian). Poltava: PUET, 2011. 362 p.
[35] Yakovlev S.V. Formalization of spatial configuration optimization problems with a special function class. Cybernetics and Systems Analysis. 2019. 55, N 4. P. 512–523.