Прискорення роботи Gurobi та CPLEX при розв’язаннi задач пошуку найкоротшого циклу чи шляху, що вiдвiдує задану кiлькiсть вершин кластерiв графа
Микола М. Корабльов${}^1$, Петро І. Стецюк${}^2$
${}^1$Київський академiчний унiверситет, Київ, Україна
${}^2$Iнститут кiбернетики iм. В.М. Глушкова НАН України, Київ, Україна
Отримано 20 квiтня 2025, у фiнальнiй формi 7 червня 2025, опубліковано 19 серпня 2025.
Анотація
Однiєю з найвiдомiших та найбiльш вивчених задач дослiдження операцiй є задача комiвояжера. Не дивлячись на свою просту постановку, вона знайшла застосування у багатьох рiзних галузях i по сьогоднi є темою активних дослiджень пов’язаних як з розробкою нових методiв та пiдходiв до ї ї розв’язання, так i зi створенням узагальнених постановок задач i нових математичних моделей для їх формалiзацiї. Дана робота присвячена дослiдженню впливу двох видiв додаткових обмежень на швидкiсть роботи програм Gurobi та CPLEX при розв’язаннi спецiального класу задач маршрутизацiї. Наведенi постановки задач пошуку найкоротшого циклу i шляху, що вiдвiдує задану кiлькiсть вершин кластерiв графа. Описанi математичнi моделi змiшаного цiлочислового лiнiйного програмування для їх розв’язання на основi обмежень Мiллера, Такера i Землiна та обмежень Гевiша i Грейвса. Наведенi результати обчислювальних експериментiв, якi демонструють вплив додаткових обмежень на швидкiсть розв’язання задач даними моделями.
Ключові слова: узагальненi задачi маршрутизацiї; задача комiвояжера; найкоротший цикл та шлях у графi; змiшане цiлочислове лiнiйне програмування; AMPL; Gurobi; CPLEX; NEOS Server.
[ pdf ] (800 kb)
[ tex ] (417 kb)
