El Problema de la Coloración de Grafos Soluciones Exactas y Heurísticas

El Dilema de la Coloración de Grafos Soluciones Exactas y Heurísticas

Explorando el problema clásico de optimización discreta a través de heurísticas constructivas personalizadas y programación entera en Python

La teoría de la coloración de grafos ocupa una posición central en las matemáticas discretas. Aparece en muchos lugares sin aparente o poca conexión con la coloración. Trata el problema fundamental de particionar un conjunto de objetos en clases, de acuerdo con ciertas reglas (Jensen & Toft, 1995).

Podemos resumir el problema de la siguiente manera: dado un grafo no dirigido G(V, E), asignar colores a cada nodo (vértice) de manera que ningún par de nodos adyacentes comparta el mismo color y se minimice la cantidad de colores utilizados. A pesar de la declaración concisa y clara, este problema es conocido por su complejidad computacional, ya que cae en la categoría de problemas NP-duros.

Debido a su complejidad combinatoria, el enfoque exacto de la Programación Lineal Entera (ILE) puede ser incapaz de resolver instancias grandes, incluso utilizando los mejores solucionadores disponibles. En tales situaciones, las heurísticas y metaheurísticas pueden ser alternativas interesantes. Aunque no pueden demostrar la optimalidad, estos métodos pueden proporcionar soluciones rápidas y de buena calidad.

En este artículo, resolveremos el Problema de Coloración de Grafos utilizando la heurística constructiva DSatur (Brélaz, 1979) y un modelo de programación lineal entera utilizando pyomo (Bynum et al., 2021) con el solucionador HiGHS. Como en otras historias, puedes encontrar el código completo en mi repositorio de código.

• Revisión de AdCreative.ai ¿La mejor herramienta de marketing de IA para anuncios?
• Integración Continua y Despliegue Continuo (CI/CD) para Sistemas IoT habilitados por AI
• Alper Tekin, Director de Productos en Findem – Serie de Entrevistas

En caso de que aún no estés familiarizado con la Programación Lineal, te recomiendo leer mi artículo anterior para obtener conocimientos fundamentales antes de continuar.

Programación Lineal: Teoría y aplicaciones

Conceptos principales de la optimización lineal e implementación en Python

towardsdatascience.com

Ahora pongamos manos a la obra para crear soluciones increíbles como esta.

Heurística constructiva – DSatur

Recordemos nuestra definición del problema:

• Considera un grafo no dirigido G(V, E).
• Asigna colores a cada nodo de manera que ningún par de nodos adyacentes comparta el mismo color.
• Minimiza la cantidad de colores utilizados.

Una solución constructiva ingenua puede consistir en elegir sucesivamente un nodo vacío y asignarle un color asegurándose de que este color aún no se haya utilizado en sus vecinos. Esa puede no ser la mejor estrategia posible, pero seguramente puede proporcionar un límite superior para la cantidad necesaria de colores. Sin embargo, el algoritmo DSatur (Brélaz, 1979) incluye nuevos elementos para elegir el siguiente nodo y mejorar esta heurística.

• Grado: Número de aristas conectadas a un nodo dado.
• Saturación: Número de colores diferentes utilizados en los vecinos.

El algoritmo DSatur comienza con una cola de nodos sin colorear y elige iterativamente un nodo con un grado de saturación máximo, lo elimina de la cola y le asigna un color. Si hay una igualdad en la saturación, Brélaz (1979) sugiere elegir cualquier nodo con saturación máxima. Elegiremos un enfoque ligeramente diferente rompiendo empates al elegir el nodo con el grado general máximo. El color asignado a un nodo dado debe ser aquel con el índice más bajo disponible. A continuación, se presenta un pseudocódigo. Considera N el conjunto de nodos, Q la cola de nodos sin colorear que referencia las mismas ubicaciones de memoria de N mismo, y C el conjunto de colores utilizados.

dsatur(N)  Q = [&n for n in N]  C = {}  while |Q| > 0:    sort(Q) // ordenar en orden descendente por saturación y grado    n = Q.pop(0)    asignar_color(n, C)

La función asignar_color debe verificar el color de índice más bajo disponible y, si ninguno del conjunto actual es viable, incluir una nueva alternativa e incrementar el conjunto.

A continuación, vamos a escribir ese código en Python. Comenzaremos con las importaciones de paquetes. Nuestra heurística se escribirá en Python puro con solo algunas importaciones de tipado.

from typing import List, Tuple

Ahora, vamos a definir nuestros elementos básicos de modelado: Colores y Nodos. La clase Color se define como un marcador mutable para los índices correspondientes de sus instancias. Esto puede ser eficiente en términos de memoria en Python, ya que varias variables pueden hacer referencia a la misma ubicación de memoria. El método add_node debe ser llamado cada vez que se colorea un nuevo nodo con un color dado.

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

Ahora la clase Node. Cada instancia de Node tiene un atributo neighbors que es una lista de nodos (punteros). Por lo tanto, cada vez que se modifica un nodo, no es necesario cambiar ninguna información en sus vecinos. Podemos agregar un vecino utilizando el método add_neighbor, establecer su color utilizando el método set_color, y acceder a propiedades que dependen del estado actual de sus vecinos como neighbor_colors, saturación y grado.

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)

Ahora el algoritmo DSatur. Para implementarlo, se creará una clase con el mismo nombre. La creación de una nueva instancia de DSatur toma como argumentos el número de nodos n_nodes y las edges aristas del grafo. Luego, instancia los nodos y establece sus vecinos en función de las aristas.

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]  # Pool of uncolored nodes        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)

Ahora vamos a usarlo para resolver algunos problemas desafiantes. Puedes encontrar varios ejemplos en la Biblioteca OR. Se denotan como “gcolX”. Podemos extraer el número de nodos y bordes de uno de esos archivos usando el siguiente código.

# Abrir y leer archivo
with open($TU_RUTA_DE_ARCHIVO, mode="r") as file:
    lines = file.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, "Número incorrecto de nodos especificados"

Luego simplemente convertimos esto en una nueva instancia DSatur y resolvemos el problema (o al menos obtenemos una aproximación de buena calidad).

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

El código para crear esa interesante visualización de los resultados de la introducción puede ser demasiado verboso para incluirlo aquí, pero puedes encontrarlo en mi repositorio de código. Puede transmitir una idea general de lo difícil que se vuelve al manejar varios nodos…

Ahora veamos cómo podríamos manejarlo mediante un enfoque exacto.

Programación Lineal Entera

Para refinar nuestras soluciones obtenidas mediante heurísticas y tratar de demostrar la optimalidad de las soluciones, formularemos el Problema de Coloreo de Grafos como un modelo de ILP. Sin embargo, recuerda que puede no ser capaz de manejar instancias grandes. El modelo presentado en esta sección y otros algoritmos exactos se presentan en el Capítulo 3 de Lewis (2021).

Definamos los conjuntos considerados en este enfoque:

• C: Colores
• N: Nodos (o vértices)
• E: Bordes

Una primera pregunta que surge es “¿Cuántos colores debemos considerar?”. En el peor de los casos, todos los nodos están conectados, por lo que se deben considerar C del mismo tamaño que N. Sin embargo, este enfoque podría dificultar aún más nuestras soluciones al aumentar innecesariamente el número de variables de decisión y empeorar la relajación lineal del modelo. Una buena alternativa es utilizar un método heurístico (como DSatur) para obtener un límite superior para el número de colores.

En este problema, tenemos dos grupos de variables de decisión:

• x_{i, c}: Son variables binarias que indican que el nodo i está coloreado con c
• y_{c}: Son variables binarias que indican que se utiliza el color c

También debemos crear restricciones para garantizar que:

• Cada nodo debe tener un color
• Si algún nodo de un borde tiene un color, asegurarse de que se esté utilizando ese color
• Como máximo, 1 nodo de cada borde puede tener un color dado
• Romper simetría (esto no es necesario, pero puede ayudar)

Finalmente, nuestro objetivo es minimizar el número total de colores utilizados, que es la suma de y. Resumiendo, tenemos las siguientes ecuaciones.

Sin más preámbulos, importemos pyomo para el modelo de Programación Entera.

import pyomo.environ as pyo

Hay dos enfoques para modelar un problema en pyomo: modelos Abstractos y Concretos. En el primer enfoque, se definen las expresiones algebraicas del problema antes de suministrar algunos valores de datos, mientras que en el segundo, se crea la instancia del modelo inmediatamente a medida que se definen sus elementos. Puedes encontrar más información sobre estos enfoques en la documentación de la biblioteca o en el libro de Bynum et al. (2021). A lo largo de este artículo, adoptaremos la formulación del modelo Concreto.

modelo = pyo.ConcreteModel()

A continuación, instanciemos nuestros Sets. El análisis directo de los iterables desde los atributos N y C de dsatur es válido, por lo que podríamos usarlos en los argumentos de palabras clave initialize. Alternativamente, pasaré los nodos y las aristas originales de nuestros datos de entrada y crearé un rango a partir de DSatur como nuestra inicialización para los colores.

modelo.C = pyo.Set(initialize=range(len(dsatur.C)))  # Coloresmodelo.N = pyo.Set(initialize=nodes)  # Nodosmodelo.E = pyo.Set(initialize=edges])  # Aristas

A continuación, instanciamos nuestras variables de decisión.

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

Y luego nuestras restricciones.

# Rellenar cada nodo con algún colorendef fill_cstr(modelo, i):    return sum(modelo.x[i, :]) == 1# No repetir colores en las aristas e indicar que se usa el colorendef edge_cstr(modelo, i, j, c):    return modelo.x[i, c] + modelo.x[j, c] <= modelo.y[c]# Romper simetría estableciendo un orden de preferencia (no es requerido)def break_symmetry(modelo, c):    if modelo.C.first() == c:        return 0 <= modelo.y[c]    else:        c_prev = modelo.C.prev(c)        return modelo.y[c] <= modelo.y[c_prev]modelo.fill_cstr = pyo.Constraint(modelo.N, rule=fill_cstr)modelo.edge_cstr = pyo.Constraint(modelo.E, modelo.C, rule=edge_cstr)modelo.break_symmetry = pyo.Constraint(modelo.C, rule=break_symmetry)

Puedes intentar incluir otras restricciones para romper la simetría y ver qué funciona mejor con tu solucionador disponible. En algunos experimentos que realicé, incluir un orden de preferencia usando el número total de nodos asignados a un determinado color fue peor que ignorarlo. Posiblemente debido a las estrategias nativas de rompimiento de simetría del solucionador.

# Romper simetría estableciendo un orden de preferencia con asignaciones totalesdef break_symmetry_agg(modelo, c):    if modelo.C.first() == c:        return 0 <= sum(modelo.x[:, c])    else:        c_prev = modelo.C.prev(c)        return sum(modelo.x[:, c]) <= sum(modelo.x[:, c_prev])

Por último, el objetivo…

# Número total de colores utilizadosdef obj(modelo):    return sum(modelo.y[:])modelo.obj = pyo.Objective(rule=obj)

¡Y nuestro modelo está listo para ser resuelto! Para hacer eso, estoy utilizando el solucionador persistente HiGHS, que está disponible en pyomo en caso de que highspy también esté instalado en tu entorno de Python.

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

Para instancias grandes, nuestro solucionador puede tener dificultades para mejorar soluciones heurísticas. Sin embargo, para una instancia de 32 nodos disponible en el repositorio de código, el solucionador pudo reducir el número de colores utilizados de 9 a 8. Vale la pena mencionar que tardó 24 segundos en completar la ejecución, mientras que el algoritmo DSatur para la misma instancia solo tardó 6 milisegundos (usando Python puro, que es un lenguaje interpretado).

Lecturas adicionales

Aunque DSatur es una heurística intuitiva que proporciona soluciones rápidas de buena calidad, otras pueden llevar a mejores resultados, especialmente en instancias complejas. Una de las metaheurísticas más famosas para el Problema de Coloración de Grafos es Tabucol (Hertz & Werra, 1987). Los autores proponen un método que parte de una solución inicial con k colores y posiblemente aristas que conectan nodos del mismo color. Luego, se realizan movimientos locales que cambian el color de un nodo dado en un sentido que minimiza las violaciones, utilizando una Lista Tabú para escapar de los óptimos locales.

Métodos exactos más eficientes para el Problema de la Coloración de Grafos que el presentado aquí se basan en la Generación de Columnas, utilizando un algoritmo conocido como Branch & Price. El lector interesado en una introducción al tema puede encontrar una visión general concisa en mi otro artículo de VoAGI.

Generación de Columnas en la Programación Lineal y el Problema del Corte de Stock

Cómo resolver problemas lineales con un gran número de variables de decisión ilustrado con un ejemplo en Python

towardsdatascience.com

Conclusiones

En este artículo se presentaron dos enfoques para resolver el Problema de la Coloración de Grafos: la heurística constructiva DSatur (Brélaz, 1979) y un modelo de Programación Lineal Entera (ILE). La heurística fue capaz de proporcionar soluciones rápidas de buena calidad para una instancia de tamaño moderado, cuya solución se mejoró aún más utilizando el modelo de ILE. El código implementado está disponible para su uso posterior en un repositorio público.

Referencias

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

We will continue to update Zepes; if you have any questions or suggestions, please contact us!