Кандидатська дисертація. Шило Петро Володимирович. Алгоритми розв'язання окремих класів задач дискретної оптимізації великої розмірності

Registration Number

0417U004117, Candidate dissertation

Status

к.ф.-м.н.

Date

27-10-2017

popup.evolution

.

Title

Algorithms for solving separate classes of large scale discrete optimization problems

Author

Shylo Petro Volodymyrovych,

popup.head Sergienko Ivan Vasylyovych
popup.opponent Михайлюк Віктор Олексійович
popup.opponent Чупов Сергій Вікторович

popup.rada

V.M.Glushkov Institute of Cybernetics of NASU

Description

Розроблено нові алгоритми розв'язання задач дискретної оптимізації великої розмірності, а саме: задач про покриття множини та про покриття множини мінімальної потужності, квадратичної задачі про призначення, задачі побудови завадозахищеного коду максимального обсягу для Z-каналу, яка зводиться до задачі знаходження максимальної незалежної множини вершин графу. Серед запропонованих є алгоритми: глобального рівноважного пошуку, випадкового локального пошуку, табу та точний алгоритм гілок і меж. На основі експериментальних досліджень проведено порівняльний аналіз кращих відомих та розроблених автором алгоритмів, який підтвердив переваги останніх за швидкодією та якістю отриманих розв'язків. З використанням портфелів та команд алгоритмів глобального рівноважного пошуку розроблено та досліджено паралельні алгоритми розв'язання задач про максимальний зважений розріз графу та булевого квадратичного програмування без обмежень, які дають змогу суттєво прискорити цей процес та розв'язувати за рахунок цього задачі великої розмірності.

Registration Date

2017-11-02

popup.nrat_date

2020-04-03 / 2026-06-29