OPTIMIZATION OF LINEAR FUNCTIONS ON A SET OF CYCLIC PERMUTATIONS WITH LINEAR CONSTRAINTS
DOI:
https://doi.org/10.26906/SUNZ.2018.3.067Keywords:
combinatorial optimization, linear function, permutations, cyclic permutations, random search, transpositionsAbstract
This paper is devoted to the solution of problems of linear and discrete optimization on various classes of combinatorial sets. In particular, the paper describes the solution of the optimization problem for a linear function with linear constraints on the set of cyclic permutations. A decision strategy is described using an algorithm based on random search. To solve the problem of optimizing a linear function on the set of cyclic permutations, we use the approach based on the ideology of random search and the analytical solution of systems of linear inequalities describing the constraints of the problem. In the process of solving the initial problem, it becomes necessary to solve the additional problem of linear optimization multiple times on a set of cyclic permutations without restrictions. The paper presents two options for solving the auxiliary problem. The first algorithm is based on the branch and bound method. Advantages of this approach are - the ability to obtain an exact solution, various variations of the branching method allow flexibly manage the computational costs. An alternative to the branch and bound method is also given in the work - a heuristic method based on transpositions of a special kind. To do this, we considered a class of transpositions characterized by the fact that transpositions from a given class correspond to the adjacency criterion in a permutation polyhedron. The proposed strategies are implemented and tested on problems of different dimensions with initial data generated randomly. Computational experiments have been performed to compare the accuracy and time of the solution of the original problem by two variations of the random search method. Experiments show the advantage of solving an auxiliary problem by the branch and bound method on small dimensions. In large-scale problems, the method based on transpositions of a special kind significantly benefits in terms of saving computational costs.Downloads
References
Сергиенко И. В. Математические модели и методы решения задач дискретной оптимизации / И. В. Сергиенко – К.: Наук. думка, 1988. – 472 с.
Емец О. А. Комбинаторная оптимизация на размещениях / О. А. Емец, Т. Н. Барболина. – К.: Наук. думка, 2008. – 159 с.
Стоян Ю. Г. Теорія і методи евклідової комбінаторної оптимізації / Ю. Г. Стоян, О. О. Ємець – К.: Інститут системних досліджень освіти, 1993. –188 с.
Стоян Ю. Г. Математические модели и оптимизационные методы геометрического проектирования / Ю. Г. Стоян, С. В. Яковлев – К.: Наук. думка, 1986. – 268 с.
Гребенник И. В. Упорядочение перестановок при решении задач комбинаторной оптимизации с линейной целевой функцией / И. В. Гребенник, Л. Ю. Юрченко // Системи обробки інформації.– Х.: ХУПС, 2007. – Вип. 8 (66).– С. 139-142.
Гребенник И. В. Решение некоторых задач условной оптимизации линейных функций на перестановочном многограннике. / И. В. Гребенник // Радиоэлектроника и информатика.– 1999.– № 1.– С. 55-59.
Емеличев В. А. Многогранники, графы, оптимизация. / В. А. Емеличев, М. М. Ковалев, М. К. Кравцов. – М.: Наука, 1981. – 344 с.
Стенли Р. Перечислительная комбинаторика / Р. Стенли; пер. с англ. А. И. Барвинка. – М.: Мир, 1990. – 440 с.
Гребенник И. В. Оптимизация линейной функции на множестве циклических перестановок / И. В. Гребенник, А. С.Литвиненко, О. С. Титова. – Бионика Интеллекта. – 2012. – № 2 (79). – С. 8-12.
Емец О. А. Решение линейных задач оптимизации на размещениях методом отсечения / О. А. Емец, Т. Н. Барболина // Кибернетика и системный анализ. – 2003. – Т. 37, № 6.
Гребенник И. В. Специальные транспозиции элементов перестановок и свойства композиции / И. В. Гребенник, О. С. Черная // Кибернетика и системный анализ.– 2017.– Т. 53, № 1. – С. 79-90.
Реклейтис Г. Оптимизация в технике / Г. Реклейтис, А. Рейвиндран, К. Рэгсдел; пер. с англ. В. Я. Алтаева. – М.: Мир, 1986. – 348 с.
Bona M. Combinatorics of permutations / M. Bona. – Chapman & Hall/CRC, 2004. – 337 c.
Гребенник И. В. Оптимизация линейных функций с линейными ограничениями на комбинаторных множествах на основе случайного поиска / И. В. Гребенник, А. В. Баранов // Искусств. интеллект. – 2007. – № 1.– С. 132-137.
