UDC 519.85
1 V.M. Glushkov Institute of Cybernetics, National Academy
of Sciences of Ukraine, Kyiv, Ukraine
|
|
A METHOD TO SOLVE THE CONDITIONAL OPTIMIZATION PROBLEM WITH
A QUADRATIC OBJECTIVE FUNCTION ON THE SET OF PERMUTATIONS
Abstract. The problem with a quadratic objetive function and additional linear constraints is considered on the set of permutations. A solution method is proposed, which consists of two stages. At the first stage, the set of support solutions is found. A quadratic function is composed for the corresponding transposition and sub-problems are generated with additional constraints. A set of supporting solutions that satisfy the constraints of the main problem can be found in the course of their solution. The second stage is to find the optimal solution from the subset of optimal solutions and the set of feasible solutions.
Keywords: conditional optimization, quadratic function, set of permutations, transposition of elements, increase in function, increase in constraint, set of feasible solutions, set of support solutions, optimal solution.
FULL TEXT
REFERENCES
- 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. A method for modeling the structure of the source data and subclasses of solvable combinatorial optimization problems. Kibernetika i sistemnyj analiz. 2014. Vol. 50, N 1. P. 3–11.
- Shor N.Z., Stetsyuk P.I. Lagrangian bounds in multiextremal polynomial and discrete optimization problems. Journal of Global Optimization. 2002. N 23. P. 1–41.
- Donetsk G.P., Kolechkin L.M. Extreme problems on combinatorial configurations [in Ukrainian]. Poltava: PUET, 2011. 362 p.
- 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.
- 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., 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.
- Korte B., Vygen J. Combinatorial optimization: Theory and Algorithms. Heidelberg; New York: Springer, 2012. 660 p.
- 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. Vol. 44, N 3. P. 441–451.
- Yakovlev S., Pichugina O., Yarovaya O. Polyhedral-spherical configurations in discrete optimization problems. Journal of Automation and Information Sciences. 2019. Vol 51, N 1. P. 26–40.
- Yakovlev S. Convex extensions in combinatorial optimization and their applications. Optimization and Applications. P. Pardalos, S. Butenco, V. Shilo (Eds.). New York: Springer, 2017. P. 501–517.
- Chase P. Transposition graphs. SIAM Journal on Computing. 1973. Vol. 2, N 2. P. 128–133. https://doi.org/10.1137/0202011.
- Ehrgott M. Multicriteria Optimization. Berlin; New York: Springer, 2005. 315 p.
- Ehrgott M., Gandibleux X. Multiobjective combinatorial optimization — theory, methodology, and applications. M. Ehrgott, X. Gandibleux (Eds.). Multiple Criteria Optimization: State of the Art Annotated Bibliographic Surveys. 2003. Vol. 52. P. 369–444. Springer US. https://doi.org/ 10.1007/0-306-48107-3_8.
- Ganesan A. Automorphism group of the complete transposition graph. Journal of Algebraic Combinatorics. 2015. Vol. 42, N 3. P. 793–801. https://doi.org/10.1007/s10801-015-0602-5.
- 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.
- 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 N.V. Elements of the theory of geometric design [in Russian]. Kyiv: Nauk. dumka, 1995. 241 p.
- Pichugina O.S. Method for constructing convex extensions of square polynomials on combinatorial sets. ZhSTU Bulletin. Engineering sciences. 2010. Vol. 53, N 2. P. 141–150.
- 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.
- Koliechkina L., Nahirna A., Dvirna O. Quadratic optimization problem on permutation set with simulation of applied tasks. 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.
- Donets G.A., Kolechkina L.N. Method of ordering the values of a linear function on a set of permutations. Cybernetics and Systems Analysis. 2009. Vol. 45, N 2, P. 204–213.
- Donec G.A., Kolechkina L.M. Construction of Hamiltonian paths in graphs of permutation polyhedra. Cybernetics and Systems Analysis. 2010. Vol. 46, N 1. P. 7–13.
- 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.
- Стоян Ю.Г., Ємець О.О. Теорія і методи евклідової комбінаторної оптимізації. Київ: Інститут системних досліджень освіти, 1993. 188 с.
- Burkard R.E. Quadratic assignment problems. P.M. Pardalos, D.-Z. Du, R.L Graham (Eds.). Handbook of combinatorial optimization. New York: Springer, 2013. P. 2741–2814. https://doi.org/10.1007/978-1-4419-7997-1_22.
