Optimization over the general signed permutation set of permutations
DOI:
https://doi.org/10.20535/SRIT.2308-8893.2017.4.07Keywords:
combinatorial optimization, the polyhedral-spherical set, signed permutations, the general permutation set, the binary set, a supersphere, the polyhedral-surface method, the conditional gradient methodAbstract
A general signed permutation set is introduced. Approaches to optimization on it that are based on its mapping into the Euclidean space are considered. In the scope of the study, properties of the Euclidean combinatorial set and its convex hull - the general signed permutohedron are derived. They include set’s cardinality, an irreducible H-representation of the polyhedron, its dimension, the vertex and adjacency vertex criteria, and the number of combinatorially nonisomorphic polyhedra of a fixed dimension. The behavior of some classes of functions over the general signed permutation set is investigated. Functional-analytical representations of this set are constructed including polyhedral-superspherical and strict superspherical. Explicit solutions of a linear problem and a projection problem over the general signed permutation set are presented. The research allows applying continuous methods to optimization on the discrete set and obtaining both exact and approximate solutions with accuracy estimates.References
Kochenberger G. The unconstrained binary quadratic programming problem: a survey / G. Kochenberger, J.-K. Hao, F. Glover etc // Journal of Combinatorial Optimization. — 2014. — N 1. — P. 58-81. DOI: 10.1007/s10878-014-9734-0.
Pichugina O. Convex extensions and continuous functional representations in optimization, with their applications / O. Pichugina, S. Yakovlev // J. Coupled Syst. Multiscale Dyn. — 2016. — Vol. 4(2) . — P. 129–152. DOI: 10.1166/jcsmd.2016.1103
Stojan Ju.G. Matematicheskie modeli i optimizatsionnye metody geometricheskogo proektirovanija / Ju.G. Stojan, S.V. Jakovlev. — K. : Nauk. dumka, 1986. — 268 s.
Stojan Ju.H. Teorija i metody evklidovoyi kombinatornoyi optymizatsiyi / Ju.H. Stojan, O. O. Yemets'. — K. : In-t systemn. doslidzh. osvity, 1993. — 188 s.
Stojan Ju.G. Nekotorye svojstva spetsial'nyh kombinatornyh mnozhestv (Preprint AN USSR/Institut problem mashinostr.; 85) / Ju.G. Stojan. — Har'kov, 1980. — 22 s.
Taha H. A. Integer Programming: Theory, Applications, and Computations. Edited by J. William Schmidt / H.A. Taha. — New York: Academic Press, 2014. — 392 p.
Sherali H.D. A reformulation-linearization technique for solving discrete and continuous nonconvex problems / H.D. Sherali, W.P. Adams, P.M. Pardalos (eds.).— Dordrecht: Kluwer Academic Publishers, 1999. — 518 p. DOI: 10.1007/978-1-4757-4388-3.
Pichugina O. Continuous Approaches to the Unconstrained Binary Quadratic Problems / O. Pichugina, S. Yakovlev // Mathematical and Computational Approaches in Advancing Modern Science and Engineering, Edited J. Bélair et al. — Springer, Switzerland. — 2016. — P. 689–700. DOI: 10.1007/978-3-319-30379-6_62.
Pichugina O.S. Continuous Representations and Functional Extensions in Combinatorial Optimization / O.S. Pichugina, S.V. Yakovlev // Cybernetics and Systems Analysis. — 2016. — Vol. 52, N 6. — P. 921–930. DOI: 10.1007/s10559-016-9894-2.
Pichugina O. Continuous Representation Techniques in Combinatorial Optimization / O. Pichugina, S. Yakovlev // IOSR Journal of Mathematics. — 2017. — Vol. 13, N 2, Ver.V. — P. 12–25. DOI: 10.9790/5728-1302051225.
Pichugina O. Optimization on Polyhedral-Spherical Sets: Theory and Applications / O. Pichugina, S. Yakovlev // In 2017 IEEE First Ukraine Conference on Electrical and Computer Engeneering (UKRCON) . — 2017. — P. 1167–1174. DOI: 10.1109/UKRCOM.2017.8100436.
Jakovlev S.V. Teorija vypuklyh prodolzhenij funktsij na vershinah vypuklyh mnogogrannikov / S. V. Jakovlev // Zhurn. vychisl. matem. i matem. fiz. — 1994. — 34, № 7. — S. 1112–1119.
Jakovlev S.V. O nekotoryh klassah zadach optimizatsii na kombinatornyh mnozhestvah razmeschenij / S.V. Jakovlev, I.V. Grebennik // Izv. vuzov. Ser. Mat. — 1991. — №11. — S. 26 – 30.
Postnikov A. Permutohedra, associahedra, and beyond / A. Postnikov // IMRN: International Mathematics Research Notices. — 2009. — N 6. — P. 1026-1106. DOI: 10.1093/imrn/rnn153.
Weisstein E.W. CRC Concise Encyclopedia of Mathematics, Second Edition / E.W. Weisstein. — Boca Raton: CRC Press, 2002. — 3242 p.
Emelichev V.A. Mnogogranniki, grafy, optimizatsija (kombinatornaja teorija mnogogrannikov) / V.A. Emelichev, M.M. Kovalev, M.K. Kravtsov. — M.: Nauka. Gl. red. fiziko-mat. lit-ry, 1981. — 344 s.
Onaka S. Superspheres: intermediate shapes between spheres and polyhedra / S. Onaka // Symmetry. — 2012. — Vol.4, N 3. — P. 336–343. DOI: 10.3390/sym4030336.
Pichugina O.S. Funktsional'no-analiticheskie predstavlenija obschego perestanovochnogo mnozhestva / O.S. Pichugina, S.V. Jakovlev // Eastern-European Journal of Enterprise Technologie. — 2016. — № 1 — S. 101–126. DOI: 10.15587/1729-4061.2016.58550.
Berstein Y. Parametric nonlinear discrete optimization over well-described sets and matroid intersections / Y. Berstein, J. Lee, S. Onn, R. Weismantel // Mathematical Programming. — 2010. — Vol. 124, N 1/2 — P. 233–253. DOI: 10.1007/s10107-010-0358-6.
Bertsekas D.P. Nonlinear Programming, 2nd edn. / D.P. Bertsekas. — Belmont: Athena Scienific, 1999. — 708 p.
Huljanyts'kyj L.F. Prykladni metody kombinatornoyi optymizatsiyi : navchal'nyj posibnyk / L.F. Huljanyts'kyj, O.Ju. Mulesa. — K: Vydavnycho-polihraf. tsentr "Kyyivs'kyj universytet", 2016. — 142 s.
Sergienko I.V. Methods of optimization and systems analysis for problems of transcomputational complexity / I.V. Sergienko. — New York: Springer, 2012. — 226 p. DOI: 10.1007/978-1-4614-4211-0.
