Оптимізація на загальній множині перестановок зі знаком

• Дата: 2017
• Автор: Pichugina, Oksana S.
• Формат: Стаття
• Мова: rus
• Опубліковано: The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2017
• Теми: combinatorial optimization; the polyhedral-spherical set; signed permutations; the general permutation set; the binary set; a supersphere; the polyhedral-surface method; the conditional gradient method; комбинаторная оптимизация; полиэдрально-сферическое множество; перестановки со знаком; общее множество перестановок; бинарное множество; суперсфера; полиэдрально-поверхностный метод; метод условного градиента; комбінаторна оптимізація; многогранно-сферична множина; перестановки зі знаком; загальна множина перестановок; бінарна множина; многогранно-поверхневий метод; метод умовного градієнта
• Онлайн доступ: http://journal.iasa.kpi.ua/article/view/103892
• Назва журналу: System research and information technologies

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.