Finding the Optimal Solution to the Problem of Conditional Optimization on the Graph of the set of Placements

• Published in: Control systems & computers
• Date: 2020
• Main Authors: Koliechkina, L.M., Nahirna, A.M.
• Format: Article
• Language: English
• Published: Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2020
• Subjects: Fundamental Problems in Computer Science
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/181233
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Finding the Optimal Solution to the Problem of Conditional Optimization on the Graph of the set of Placements / L.M. Koliechkina, A.M. Nahirna // Control systems & computers. — 2020. — № 6. — С. 29-34. — Бібліогр.: 17 назв. — англ.

An optimization problem on a combinatorial set of partial permutations with additional constraints is formulated in the paper. An algorithm for solving this type of problem is considered, which consists of four steps. The algorithm lies in constructing a graph of a set of partial permutations to find the optimal solution. An example of a practical implementation of the presented algorithm is given. Мета статті — представлення методу розв’язання задачі умовної оптимізації на графі множини розміщень і демонстрація практичного прикладу реалізації. Методи. Метод розв’язання комбінаторної задачі з додатковими обмеженнями на графі. Результати. Сформульовано модель задачі умовної оптимізації на множині розміщень. Одержано лінійну форму цільової функції шляхом інтерпретації елементів множини розміщень як точок евклідового простору. Розглянуто комбінаторний многогранник розміщень, для якого існує граф множини розміщень. Запропоновано алгоритм розв’язання даної задачі та продемонстровано його практичне застосування. Целью данной статьи является представление метода решения задачи условной оптимизации на графе множества размещений и демонстрация практического примера реализации. Методы. Метод решения комбинаторной задачи с дополнительными ограничениями на графе. Результаты. Сформулирована модель задачи условной оптимизации на множестве размещений. Получена линейная форма целевой функции путем интерпретации элементов множества размещений, как точек евклидова пространства. Рассмотрен комбинаторный многогранник размещений, для которого существует граф множества размещений. Предложен алгоритм решения данной задачи и продемонстрирована его практическая применимость.