UDC 519.85
SOLUTIONS OF THE COMBINATOR PROBLEM WITH A FRACTIONAL-QUADRATIC
OBJECTIVE FUNCTION ON THE SET OF PERMUTATIONS
Abstract. The statement of the problem with fractional-quadratic objective function on the set of permutations is considered.
An algorithm for its solution is presented, which converts the fractional-quadratic function into a system of two functionals.
The solution of these functionals ensures finding the optimal solution to the problem. The results of computational experiments are presented.
Keywords: conditional optimization, fractional-quadratic function, many permutations, transposition of elements, set of feasible solutions, set of support solutions, optimal solution.
FULL TEXT
REFERENCES
- Korte B., Vygen J. Combinatorial optimization: Theory and algorithms. Heidelberg; New York: Springer, 2012. 660 p.
- Onwubolu G.C., Davendra D. Differential evolution: A handbook for global permutation-based combinatorial optimization. Berlin; Heidelberg: Springer-Verlag, 2009. 213 p.
- Pardalos P.M., Du D., Graham R.L. Handbook of combinatorial optimization. New York: Springer, 2013. 648 p.
- Gulianitsky L.F., Sergienko, I.V. Meta-evolutionary method of deformed polyhedron in combinatorial optimization. Cybernetics and Systems Analysis. 2007. Vol. 44, N 6. Р. 70–79.
- Donets G.A., Sergienko I.V. The method of modeling the structure of the source data and subclasses of solvable combinatorial optimization problems. Kibernetika i sictemnyj analiz. 2014. Т. 50. N 1. P. 3–11.
- Stoyan Y.G., Yakovlev S.V., Parshin O.V. Quadratic optimization on combinatorial sets in . Cybernetics and Systems Analysis. 1991. Vol. 27, N 4, Р. 561–567.
- Yakovlev S.V., Gil N.I., Komyak V.M., Aristova I.V. Elements of the theory of geometric design [in Russian]. Kyiv: Nauk. dumka, 1995. 241 p.
- Shor N.Z., Stetsyuk P.I. Lagrangian bounds multiextremal polynomial and discrete optimization problems. Journal of Global Optimization. 2002. N 23. P. 1–41.
- Donets G.P., Kolechkina L.M. Extremal problems on combinatorial configurations [in Ukrainian]. Poltava: PUET, 2011. 362 p.
- Emelichev V.A., Kovalev M.M., Kravtsov M.K. Polyhedra, graphs, optimization [in Russian]. Moscow: Nauka, 1981. 344 p.
- Stoyan Yu.G., Yakovlev S.V. Mathematical models and optimization methods of geometric design [in Russian]. Kyiv: Nauk. dumka, 1986. 265 p.
- Stoyan Y.G., Yemets O.O. Euclidean combinatorial optimization theory and methods [in Ukrainian]. Kyiv: ISDO, 1993. 188 p.
- 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.
- 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.
- Koliechkina L., 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.
- Donets G.A., Kolechkina L.N. On a problem of optimization of a linear linear fractional function on permutations. Problemy upravleniya i informatiki. 2010. N 2. P. 12–16.
- Emets O.A., Kolechkina L.N. Solving optimization problems with linear fractional objective functions and additional linear constraints on permutations. Kibernetika i sictemnyj analiz. 2004. N 3. P. 156–169.
- Shor N.Z., Solomon D.I. Decomposition methods in linear fractional programming [in Russian]. Chisinau: Stiince, 1989. 204 p.
- Sergienko I.V., Kaspshitskaya M.F. Models and methods for solving computer-based combinatorial optimization problems [in Russian]. Kiev: Nauk. dumka, 1981. 287 p.
- Emets O.A., Chernenko O.A. Optimization of linear fractional functions on placements [in Russian]. Kyiv: Nauk. dumka, 2011. 154 p.
- Semenova N.V., Kolechkin LM., Nagirna A.M. Solving vector optimization problems with fractional-linear criteria functions on a combinatorial set of polylocations. Science. news of Nat. tech. University of Ukraine “Kyiv Polytechnic Institute”. 2009. N 2. P. 53–60.
- Semenova N.V., Kolechkina L.N., Nagornaya A.N. On an approach to solving vector problems with linear linear fractional functions on a combinatorial set of allocations. Problemy upravleniya i informatiki. 2010. N 1. P. 131–144.
- Koliechkina L., Nahirna A., Dvirna O. Quadratic optimization problem on permutation set with simulation of applied tasks [Electronic resource]. Proceedings of the Second International Workshop on Computer Modeling and Intelligent Systems (CMIS-2019). Zaporizhzhia, Ukraine, April 15–19, 2019. P. 651–663. (CEUR Workshop Proceedings, Vol. 2353). URL: http://ceur-ws.org/ Vol-2353/paper52.pdf.
- Burkard R.E. Quadratic Assignment Problems. In: Pardalos P.M., Du D.–Z., and Graham R.L. (eds.) Handbook of Combinatorial Optimization. New York: Springer. 2013. P. 2741–2814. https://doi.org/10.1007/978-1-4419-7997-1_22.
- Amaral P., Bomze I., Judice J. Copositivity and constrained fractional quadratic problems. Mathematical Programming. 2014. Vol. 146. P. 325–350.
- Kolechkina L.N., Nagornaya A.N., Semenov V.V. A method for solving the combinatorial problem of conditional optimization on a combinatorial set of allocations. Problemy upravleniya i informatiki. 2019. N 4. P. 62–72.
