web address of the page http://jnas.nbuv.gov.ua/article/UJRN-0001335519
Cybernetics and Systems Analysis   А - 2019 /  Issue (2022, Т. 58, № 4)
Стецюк П. І., Хом'як О. М., Блохін Є. А., Супрун А. А.
Оптимізаційні задачі для максимального k-плекса Побудовано квадратичну оптимізаційну задачу для знаходження максимального k-плекса у неорієнтованому графі. Наведено 2 сімейства функціонально надлишкових квадратичних обмежень, які отримано за допомогою обмежень Булевої задачі для максимального k-плекса. Досліджено вплив функціонально надлишкових обмежень на покращання точності Лагранжевих двоїстих оцінок для цільової функції квадратичної задачі. Розроблено алгоритм пошуку всіх максимальних k-плексів і наведено результати тестових експериментів для його реалізації за допомогою програмного пакета GLPK (GNU Linear Programming Kit).
 https://doi.org/10.1007/s10559-022-00488-5
 Scopus
Бібліографічний опис:
Стецюк П. І., Хом'як О. М., Блохін Є. А., Супрун А. А. Оптимізаційні задачі для максимального k-плекса. Кібернетика та системний аналіз. 2022. Т. 58, № 4. С. 46–58. doi: https://doi.org/10.1007/s10559-022-00488-5 URL: http://jnas.nbuv.gov.ua/article/UJRN-0001335519 |
 Cybernetics and Systems Analysis / Issue (2022, 58 (4))
Stetsyuk P.I.,
Khomiak O.M.,
Blokhin Y.A.,
Suprun A.A.
Optimization problems for the maximum k-plex The quadratic optimization problem for finding the maximum k-plex in an undirected graph is constructed. Two families of superfluous quadratic constraints obtained by means of constraints of the Boolean linear programming problem for the maximum k-plex are presented. The influence of superfluous constraints on the improvement of the accuracy of Lagrangian dual bounds for the objective function of the quadratic problem is investigated. The algorithm for searching all the maximum k-plexes is developed and the results of test experiments for its implementation using the GLPK (GNU Linear Programming Kit) software package are presented. © 2022, Springer Science+Business Media, LLC, part of Springer Nature. Keywords: Boolean linear programming problem, Lagrangian dual bound, maximum clique, maximum k-plex, quadratic optimization problem, superfluous constraint, Constrained optimization, Lagrange multipliers, Open source software, Quadratic programming, Software testing, Undirected graphs, Boolean linear programming problem, Dual bound, Lagrangian dual, Lagrangian dual bound, Linear programming problem, Maximum clique, Maximum k-plex, Optimization problems, Quadratic optimization problems, Superfluous constraint, Linear programming
Cite:
Stetsyuk P.I.,
Khomiak O.M.,
Blokhin Y.A.,
Suprun A.A.
(2022). Optimization problems for the maximum k-plex. Cybernetics and Systems Analysis, 58 (4), 46–58. doi: https://doi.org/10.1007/s10559-022-00488-5 http://jnas.nbuv.gov.ua/article/UJRN-0001335519 [In Ukrainian]. |
PDF