Рассматривается класс задач о размещениях (location problem), в рамках которого задача ставится на двудольном графе. Вершины одной доли графа интерпретируют клиентов, вершины другой – производства, обслуживающие клиентов. Требуется закрыть максимальное число производств так, чтобы число недовольных клиентов не превысило некоторый заранее заданный порог. Данная постановка соответствует т.н. BLP (Branch Location Problem). В работе описана сводимость BLP к проблемам ILP (целочисленное линейное программирование) и MaxSAT (проблема максимальной выполнимости). Для решения задачи, помимо полных алгоритмов, используется метаэвристический алгоритм, основанный на принципе склеивания переменных. Приводится сравнение эффективности использованных методов применительно к BLP.

Хабаров М.А. (науч. рук. Семёнов А.А.) Решение вариантов задачи о размещениях при помощи метаэвристики склеивания переменных // Сборник тезисов докладов конгресса молодых ученых. Электронное издание. – СПб: Университет ИТМО, [2026]. URL: https://kmu.itmo.ru/digests/article/17226