Control Systems and Computers, N6, 2019, Article 2
https://doi.org/10.15407/csc.2019.06.021
Control Systems and Computers, 2019, Issue 6 (284), pp. 21-27.
UDK 364.2:331; 681.513
A.N. Nahirna, PhD, Physical and mathematical, Associate Professor, National University of “Kyiv-Mohyla Academy”, 2 Skovoroda st., Kyiv, 04070, Ukraine naghirnaalla@ukr.net
Quadratic Problem on Combinations Set and
Method of its Solution
Introduction. When modeling different kinds of processes and phenomena in different spheres of activity, the models that represent quadratic problems of conditional optimization are used quite often. Particularly noteworthy are models of such problems considered on combinatorial sets, in particular, combinations. Despite the simplicity of presentation, this type of problem are cumbersome, from a computational point of view. Therefore, there is a need to build new methods and an algorithm for solving them.
Purpose. The purpose of this article is to present a method for solving a quadratic problem with the additional constraints on many combinations. This method allows for a finite number of steps to find the optimal solution of the formulated problem. The use of this method is shown in the numerical example.
Methods. Methods for solving a problem with a quadratic objective function on combinations set.
Results. An optimization problem on a set of combinations with a quadratic objective function and additional constraints is formulated. The method of its solution is proposed, which consists of finding the basic solutions, using the properties of the multiple combinations, as well as finding the increments of constraints and function of the goal. An example of solving a problem using the proposed method is presented.
Conclusion. The proposed method can be used to solve the conditional optimization problems with a quadratic objective function on a set of combinations.
Download full text! (In English).
Keywords: optimization, quadratic problem, quadratic function, set combinations, increment of goal function, increment of additional constraint, reference solution, optimal solution.
- Sergienko, I.V., Shilo, V.P., 2016. “Modern approaches to solving complex discrete optimization problems”. J. of Automation and Information Sciences. Vol. 48, N 1, pp. 15-24.
https://doi.org/10.1615/JAutomatInfScien.v48.i1.30 - Zgurovskiy, M.Z., Pavlov, A.A., 2016. Trudnoreshayemyye zadachi kombinatornoy optimizatsii v planirovanii i prinyatii resheniy. Kiyv : Nauk. dumka, 715 p. (In Russian).
- Colbourn, C.J., Dinitz, J.H., 2010. Handbook of Combinatorial Designs, Second Edition. CRC Press, 2010. 784 p.
- Korte, B., Vygen, J., 2018. Combinatorial Optimization: theory and algorithms. Heidelberg; New York : Springer. 698 p.
https://doi.org/10.1007/978-3-662-56039-6 - Pardalos, P.M., Du, D-Z., Graham, R.L., 2013. Handbook of combinatorial optimization. NewYork: Springer. 3409 p.
https://doi.org/10.1007/978-1-4419-7997-1 - Papadimitriou, C.H., Steiglitz, K., 2013. Combinatorial optimization: algorithms and complexity. Mineola: Dover Publications. 528 p.
- Hulianytskyi, L., Riasna, I., 2017. “Formalization and classification of combinatorial optimization problems”. Optimization Methods and Applications. Springer, New York, pp. 239-250.
https://doi.org/10.1007/978-3-319-68640-0_11 - Gulianitsky, L.F. Sergienko, I.V., 2007. “Meta-evolutionary method of deformed polyhedron in combinatorial optimization”. Cybernetics and system analysis, 44(6), pp. 70-79.
- Pichugina, O.S., Yakovlev, S.V., 2016. “Continuous Representations and Functional Extensions in Combinatorial Optimization”. Cybernetics and Systems Analysis. Vol. 52, N 6, pp. 921-930.
https://doi.org/10.1007/s10559-016-9894-2 - Stoyan, Y.G., Yakovlev, S.V., Parshin, O.V., 1991. Quadratic optimization on combinatorial sets in Rn. Cybernetics and Systems Analysis. Vol. 27, N 4, pp.562-567.
https://doi.org/10.1007/BF01130367 - Yakovlev, S.V., Pichugina, O.S., 2018. Properties of Combinatorial Optimization Problems Over Polyhedral-Spherical Sets. Cybernetics and Systems Analysis. Vol. 54, N 1, pp. 99-109.
https://doi.org/10.1007/s10559-018-0011-6 - Stoyan,Yu.G., Sokolovskii, V.Z., Yakovlev, S.V., 1982. “Method of balancing rotating discretely distributed masses”. Energomashinostroenie, N 2, pp. 4-5.
- Yakovlev, S.V., Grebennik, I.V., 1993. “Localization of solutions of some problems of nonlinear integer optimization”. Cybernetics and Systems Analysis. 1993. Vol. 29, N 5, pp. 419-426.
https://doi.org/10.1007/BF01125802 - Semenova, V., Kolechkina, L.N., Nagirna, A.N., 2008. “An approach to solving discrete vector optimization problems over a combinatorial set of permutations.” Cybernetics and Systems Analysis. Vol. 44, N 3, pp. 441-451.
https://doi.org/10.1007/s10559-008-9016-x - Koliechkina, L. N., Dvirna, O. A., Nagornaya, A.N., 2014. Modified Coordinate Method to Solve Multicriteria Optimization Problems on Combinatorial Configurations. Cybernetics and Systems Analysis. Vol. 59, N 4, pp. 620-626.
https://doi.org/10.1007/s10559-014-9650-4 - Donets, G.P., Kolechkina, L.M., 2011. “Ekstremalni zadachi na kombinatornyh konfihuratsiyah”. Poltava: RVV PUYET, 309 p. (In Ukrainian).
- Kolechkina, L.N., Nagornaya, A.N., Semenova, V.V., 2019. “Metod resheniya zadachi uslovnoy optimizatsii na kombinatornom mnozhestve razmeshcheniy”. Problemy upravleniya i informatiki. N 4, pp. 62-72. (In Russian).
- Stoyan, Yu. G., Yakovlev, C.V., Pichugina, O.S., 2017. Yevklidovy kombinatornyye konfiguratsii: monografiya. Kharkov : Konstanta. 404 p. (In Russian).
- Yakovlev, S.V., 2018. “On some classes of spatial configurations of geometric objects and their formalization”. Journal of Automation and Information Sciences. Vol. 50, N 9, pp. 38-50.
https://doi.org/10.1615/JAutomatInfScien.v50.i9.30 - Yakovlev, S., Pichugina, O., Yarovaya, O., 2019. “Polyhedral spherical configuration in discrete optimization”. JournalofAutom. andInformationSci. 2019. Vol. 51, N 1, pp. 38-50.
https://doi.org/10.1615/JAutomatInfScien.v51.i1.30
Received 03.12.2019
