Проблема раскраски графов точные и эвристические решения

Решение проблемы раскраски графов точность и эвристика

Изучение классической задачи дискретной оптимизации с помощью пользовательских конструктивных эвристик и целочисленного программирования в Python

Теория раскраски графов занимает центральное место в дискретной математике. Она применяется во многих областях, которые кажутся не имеющими связи с раскраской. Она решает фундаментальную задачу разбиения множества объектов на классы в соответствии с определенными правилами (Jensen & Toft, 1995).

Мы можем сформулировать задачу следующим образом: для заданного неориентированного графа G(V, E) назначить цвета каждому узлу (вершине) так, чтобы никакие два смежных узла не имели одинакового цвета и число использованных цветов было минимальным. Несмотря на лаконичность и ясность формулировки, эта задача славится своей вычислительной сложностью и относится к классу NP-трудных проблем.

Из-за комбинаторной сложности точный подход с помощью целочисленного линейного программирования (ILP) может быть неспособен решать большие экземпляры даже при использовании лучших имеющихся решателей. В таких ситуациях, эвристики и метаэвристики могут быть интересными альтернативами. Хотя они не могут доказать оптимальность, эти методы могут предоставить быстрые решения хорошего качества.

В этой статье мы будем решать задачу раскраски графа с использованием конструктивной эвристики DSatur (Brélaz, 1979) и модели целочисленного линейного программирования с использованием библиотеки pyomo (Bynum et al., 2021) и решателя HiGHS. В моем репозитории с кодом вы можете найти полный код для этой статьи и других материалов.

• Понимание прогнозного обслуживания — единичные корни и стационарность
• «Использование машинного обучения в управлении данными»
• Исследование роли алгоритмов консенсуса в проектировании распределенных систем

Если вы еще не знакомы с линейным программированием, я рекомендую прочитать мою предыдущую статью для основных знаний перед продолжением.

Линейное программирование: Теория и применение

Основные концепции линейной оптимизации и их реализация в Python

towardsdatascience.com

Теперь давайте перейдем к созданию удивительных решений, подобных этому.

Конструктивная эвристика — DSatur

Вспомним определение нашей задачи:

• Рассмотрим неориентированный граф G(V, E).
• Назначим цвета каждому узлу так, чтобы никакие два смежных узла не имели одинакового цвета.
• Минимизируем количество использованных цветов.

Наивное конструктивное решение может заключаться в последовательном выборе пустого узла и назначении ему цвета, учитывая то, что этот цвет еще не использовался у его соседей. Это может быть не самая лучшая возможная стратегия, но она может дать верхнюю границу для необходимого числа цветов. Однако алгоритм DSatur (Brélaz, 1979) включает новые элементы для выбора следующего узла и улучшения этой эвристики.

• Степень: Количество ребер, соединенных с данным узлом.
• Насыщенность: Количество разных цветов, использованных среди соседей.

Алгоритм DSatur начинается с очереди неназначенных узлов и итеративно выбирает узел с максимальной насыщенностью, удаляет его из очереди и назначает ему цвет. Если есть равенство насыщенности, Brélaz (1979) предлагает выбрать любой из узлов с максимальной насыщенностью. Мы выберем несколько другой подход, выбирая узел с максимальной общей степенью при равенстве насыщенности. Цвет, назначенный данному узлу, должен быть с наименьшим доступным индексом. Ниже представлен псевдокод. При его реализации учтите, что N – множество узлов, Q – очередь неназначенных узлов, ссылается на те же ячейки памяти, что и N, а C – множество использованных цветов.

dsatur(N)  Q = [&n для n в N]  C = {}  пока |Q| > 0:    сортировка(Q) // сортировка по насыщенности и степени в убывающем порядке    n = Q.pop(0)    assign_color(n, C)

Функция assign_color должна проверить наличие самого низкого доступного индекса цвета и, если ни один из текущего набора не подходит, включить новый вариант и увеличить набор.

Давайте тогда запишем это в код на Python. Начнем с импорта пакетов. Наш эвристический алгоритм будет написан на чистом Python только с некоторыми импортами для подсказки типов.

from typing import List, Tuple

Теперь давайте определим основные элементы моделирования: Цвета и Узлы. Класс Color определен, чтобы быть изменяемым заполнителем для соответствующих индексов своих экземпляров. Это может быть памяти-эффективным в Python, так как несколько переменных могут ссылаться на одно и то же местоположение в памяти. Метод add_node должен вызываться каждый раз, когда для данного цвета раскрашивается новый узел.

class Color:    index: int    n_nodes: int    def __init__(self, index) -> None:        self.index = index        self.n_nodes = 0    def __repr__(self):        return f"C{self.index}"    def add_node(self):        self.n_nodes = self.n_nodes + 1

Теперь класс Node. У каждого экземпляра Node есть атрибут neighbors, который является списком узлов (указателей). Таким образом, каждый раз, когда узел изменяется, нам не нужно изменять какую-либо информацию в его соседях. Мы можем добавить соседа с помощью метода add_neighbor, установить его цвет с помощью метода set_color и получить доступ к свойствам, которые зависят от текущих состояний их соседей neighbor_colors, saturation и degree.

class Node:    neighbors: List['Node']    index: int    color: Color    def __init__(self, index):        self.index = index        self.neighbors = []        self.color = None    def __repr__(self) -> str:        return f"N{self.index}|{self.color}"    def add_neighbor(self, node: 'Node'):        if node not in self.neighbors:            self.neighbors.append(node)    def set_color(self, color: Color):        self.color = color        color.add_node()    @property    def neighbor_colors(self):        return [n.color for n in self.neighbors if n.color is not None]    @property    def saturation(self):        return len(set((n.color for n in self.neighbors if n.color is not None)))    @property    def degree(self):        return len(self.neighbors)

Теперь алгоритм DSatur. Для его реализации будет создан класс с тем же именем. Создание нового экземпляра DSatur принимает в качестве аргументов количество узлов n_nodes и edges графа. Затем он создает узлы и устанавливает их соседей на основе ребер.

class DSatur:    N: List[Node]    C: List[Color]    history: List[Node]    def __init__(self, nodes: List[int], edges: List[Tuple[int, int]]):        N = [Node(i) for i in nodes]        for e in edges:            i, j = e            N[i].add_neighbor(N[j])            N[j].add_neighbor(N[i])        self.N = N        self.C = []        self.history = []    def find_next_color(self, node: Node) -> Color:        next_color = None        for c in self.C:            if c not in node.neighbor_colors:                next_color = c                break        if next_color is None:            next_color = Color(len(self.C) + 1)            self.C.append(next_color)        return next_color    def solve(self, save_history=False):        Q = [n for n in self.N]  # Пул непокрашенных узлов        while len(Q) > 0:            Q.sort(key=lambda x: (x.saturation, x.degree), reverse=True)            n: Node = Q.pop(0)            next_color = self.find_next_color(n)            n.set_color(next_color)            if save_history:                self.history.append(n)        self.C.sort(key=lambda x: x.n_nodes, reverse=True)    @property    def cost(self):        return len(self.C)

Теперь давайте используем его для решения некоторых сложных задач! Вы можете найти несколько примеров в библиотеке OR. Они обозначены как “gcolX”. Мы можем извлечь количество узлов и ребер из одного из этих файлов, используя следующий код.

# Открываем и читаем файл
with open($YOUR_FILE_PATH, режим="r") as файл:
    lines = файл.readlines()
    header = lines[0].strip().split()
    n_nodes = int(header[2])
    edges = []
    node_set = set()
    for line in lines[1:]:
        if line.startswith('e'):
            _, i, j = line.strip().split()
            edges.append((int(i), int(j)))
            node_set.add(int(i))
            node_set.add(int(j))
nodes = sorted(node_set)
assert len(nodes) == n_nodes, "Неверное количество указанных узлов"

Затем мы просто парсим их в новый экземпляр DSatur и решаем проблему (или, по крайней мере, получаем хорошее приближение к оптимальному решению).

dsatur = DSatur(nodes, edges)
dsatur.solve()

Код для создания интересной визуализации результатов из введения может быть слишком объемным, чтобы включить его здесь, но вы можете найти его в моем репозитории с кодом. Он может дать общую представление о том, насколько сложно работать с несколькими узлами…

Теперь посмотрим, как мы можем справиться с ней с помощью точного подхода.

Целочисленное линейное программирование

Чтобы уточнить наши решения, полученные с использованием эвристик, и попытаться доказать оптимальность решений, давайте сформулируем проблему раскраски графа как модель целочисленного линейного программирования. Однако стоит учесть, что этот подход может оказаться неспособным обрабатывать большие объемы данных. Модель, представленная в этом разделе, а также другие точные алгоритмы, описаны в главе 3 книги Льюиса (2021).

Определим наборы, рассматриваемые в этом подходе:

• C: Цвета
• N: Узлы (или вершины)
• E: Ребра

Возникает первый вопрос: “Сколько цветов следует учитывать?”. В худшем случае все узлы связаны, поэтому стоит рассмотреть C такого же размера, как N. Однако такой подход может усложнить наши решения путем необоснованного увеличения количества переменных решения и ухудшения линейной релаксации модели. Хорошей альтернативой является использование эвристического метода (например, DSatur) для получения верхней границы для количества цветов.

В этой проблеме у нас есть две группы переменных решения:

• x_{i, c}: Бинарные переменные, указывающие, что узел i раскрашен в цвет c
• y_{c}: Бинарные переменные, указывающие, что цвет c используется

Мы также должны создать ограничения, чтобы гарантировать, что:

• Каждый узел должен быть раскрашен
• Если у любого узла из одного ребра есть цвет, гарантировать, что цвет используется
• Максимум 1 узел каждого ребра может быть раскрашен в определенный цвет
• Снять симметрию (это необязательно, но может помочь)

Наконец, наша цель – минимизировать общее количество использованных цветов, которое является суммой y. В итоге у нас есть следующие уравнения.

Без лишних слов, давайте импортируем pyomo для модели целочисленного программирования.

import pyomo.environ as pyo

Существуют два подхода к моделированию задачи в pyomo: абстрактная и конкретная модели. В первом подходе алгебраические выражения проблемы определяются до предоставления некоторых значений данных, тогда как во втором экземпляр модели создается немедленно, по мере определения ее элементов. Вы можете узнать больше об этих подходах в документации библиотеки или в книге Байнума и др. (2021). В течение этой статьи мы будем использовать конкретную формулировку модели.

модель = pyo.ConcreteModel()

Затем давайте создадим экземпляры наших Множеств. Разбор итерируемых объектов напрямую из атрибутов N и C dsatur является допустимым, поэтому их можно использовать в аргументах ключевого слова initialize. В противном случае, я передам исходные узлы и ребра из наших входных данных и создам диапазон от DSatur в качестве нашей инициализации для цветов.

model.C = pyo.Set(initialize=range(len(dsatur.C)))  # Цвета
model.N = pyo.Set(initialize=nodes)  # Узлы
model.E = pyo.Set(initialize=edges])  # Ребра

Далее, мы создаем экземпляры наших переменных принятия решений.

model.x = pyo.Var(model.N, model.C, within=pyo.Binary)
model.y = pyo.Var(model.C, within=pyo.Binary)

И затем создаем наши ограничения.

# Заполняем каждый узел некоторым цветом
def fill_cstr(model, i):
    return sum(model.x[i, :]) == 1

# Не повторяем цвета на ребрах и индикатор, что цвет используется
def edge_cstr(model, i, j, c):
    return model.x[i, c] + model.x[j, c] <= model.y[c]

# Прерывание симметрии, установка предпочтительного порядка (необязательно)
def break_symmetry(model, c):
    if model.C.first() == c:
        return 0 <= model.y[c]
    else:
        c_prev = model.C.prev(c)
        return model.y[c] <= model.y[c_prev]

model.fill_cstr = pyo.Constraint(model.N, rule=fill_cstr)
model.edge_cstr = pyo.Constraint(model.E, model.C, rule=edge_cstr)
model.break_symmetry = pyo.Constraint(model.C, rule=break_symmetry)

Вы можете попробовать включить другие ограничения, нарушающие симметрию, и посмотреть, что работает лучше с вашим доступным решателем. В некоторых экспериментах, выполненных мной, включение предпочтительного порядка, используя общее количество узлов, назначенных определенному цвету, было хуже, чем его игнорирование. Возможно, из-за встроенных стратегий решателя по нарушению симметрии.

# Прерывание симметрии с учетом общего количества назначений
def break_symmetry_agg(model, c):
    if model.C.first() == c:
        return 0 <= sum(model.x[:, c])
    else:
        c_prev = model.C.prev(c)
        return sum(model.x[:, c]) <= sum(model.x[:, c_prev])

Наконец, цель…

# Общее количество использованных цветов
def obj(model):
    return sum(model.y[:])

model.obj = pyo.Objective(rule=obj)

И наша модель готова к решению! Для этого я использую постоянный решатель HiGHS, который доступен в pyomo, если highspy также установлен в вашей среде Python.

solver = pyo.SolverFactory("appsi_highs")
solver.highs_options["time_limit"] = 120
res = solver.solve(model)
print(res)

Для больших экземпляров наш решатель может испытывать трудности с улучшением эвристических решений. Однако для экземпляра с 32 узлами, доступного в репозитории кода, решатель смог сократить количество использованных цветов с 9 до 8. Стоит отметить, что это заняло 24 секунды для завершения выполнения, тогда как алгоритм DSatur для этого же экземпляра занял всего 6 миллисекунд (используя чистый Python, который является интерпретируемым языком).

Дополнительная информация

Хотя DSatur является интуитивной эвристикой, предоставляющей быстрые решения хорошего качества, другие эвристики могут привести к лучшим результатам, особенно на сложных экземплярах. Одной из наиболее известных метаэвристик для Проблемы раскраски графа является Tabucol (Hertz & Werra, 1987). Авторы предлагают метод, который начинается с начального решения с k цветами и, возможно, ребрами, соединяющими узлы того же цвета. Затем выполняются локальные перемещения, меняющие цвет заданного узла таким образом, чтобы минимизировать нарушения, с использованием списка табу для выхода из локальных оптимумов.

Более эффективные точные методы решения проблемы раскраски графа, чем представленный здесь, основаны на Column Generation с использованием алгоритма, обозначаемого как Branch & Price. Читатель, заинтересованный во введении в эту тему, может найти краткий обзор в моей другой статье VoAGI.

Генерация столбцов в линейном программировании и проблема раскроя

Как решать линейные задачи с большим количеством переменных принятия решений на примере Python

towardsdatascience.com

Выводы

В этой статье были представлены два подхода к решению проблемы раскраски графа: конструктивный эвристический метод DSatur (Brélaz, 1979) и целочисленная линейная модель программирования (ILP). Эвристика позволила быстро получить качественные решения для умеренного размера задачи, решение которой было далее улучшено с использованием модели ILP. Реализованный код доступен для дальнейшего использования в общедоступном репозитории.

Ссылки

Brélaz, D., 1979. New methods to color the vertices of a graph. Communications of the ACM, 22(4), 251–256.

Bynum, M. L. et al., 2021. Pyomo-optimization modeling in Python. Springer.

Hertz, A., & Werra, D. D., 1987. Using tabu search techniques for graph coloring. Computing, 39(4), 345–351.

Jensen, T. R., & Toft, B., 1995. Graph coloring problems. John Wiley & Sons.

Lewis, R.M.R., 2021. Advanced Techniques for Graph Colouring. In: Guide to Graph Colouring. Texts in Computer Science. Springer, Cham. https://doi.org/10.1007/978-3-030-81054-2_4