Целевой выбор ветвления для задачи максимального независимого множества с использованием графовых нейронных сетей

Нахождение максимального независимого множества — фундаментальная NP-трудная задача с многочисленными прикладными сценариями; она заключается в поиске наибольшего множества вершин неориентированного графа, попарно не смежных друг с другом. В последние годы алгоритмы ветвления и границ (branch-and-bound) и ветвления с редукцией (branch-and-reduce) стали одними из наиболее эффективных точных методов. В частности, парадигма branch-and-reduce, объединяющая принципы branch-and-bound с правилами редукции, оказалась особенно успешной на ранее неразрешимых реальных экземплярах задач — прогресс, во многом обеспеченный более эффективными правилами редукции. Тем не менее другие ключевые компоненты, влияющие на эффективность решателей, получили меньше внимания, в частности стратегия ветвления, определяющая, по какой вершине выполнять разветвление следующим. До недавнего времени стандартной эвристикой был выбор вершины с наибольшей степенью. В данной работе мы предлагаем подход на основе графовых нейронных сетей для выбора следующей вершины ветвления. Поскольку сложность современных решателей branch-and-bound затрудняет применение методов супервизированного и реверсного обучения, мы развиваем параметры модели с помощью популяционно-ориентированного генетического алгоритма. Наш подход обеспечивает ускорение в 73% тестовых экземпляров с медианным ускорением 24%.