1exxr8nxcjisibuxyft1vxw.png

Para refinar nuestras soluciones obtenidas utilizando heurísticas y tratar de demostrar la optimidad de las soluciones, formulemos el problema de coloración de gráficos como un modelo ILP. Recuerde que es posible que no pueda manejar instancias grandes. El modelo presentado en esta sección y otros algoritmos exactos se presentan en Capítulo 3 de Lewis (2021).

Definamos la Conjuntos considerado en este enfoque:

  • C: Colores
  • norte: Nodos (o vértices)
  • mi: Bordes

Ya surge una primera pregunta “¿Cuántos colores debemos considerar?”. En el peor de los casos, todos los nodos están conectados, por lo que se debe considerar C del mismo tamaño que norte. 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 en C
  • y_{C}: Son variables binarias que indican ese color. C se utiliza

También debemos crear restricciones para garantizar que:

  • Cada nodo debe estar coloreado.
  • Si algún nodo de un borde tiene un color, asegúrese de que se esté utilizando el color
  • Como máximo, 1 nodo de cada borde se puede colorear con un color determinado.
  • Romper la simetría (esto no es necesario, pero podría ayudar)

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

Modelo de programación entera para colorear gráficos. (Imagen del autor).

Sin más preámbulos, importemos piomo para el modelo de programación entera.

import pyomo.environ as pyo

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

model = pyo.ConcreteModel()

Entonces, instanciamos nuestro Conjuntos. Analizando los iterables directamente desde dsatur atributos N y C es válido, por lo que se podrían utilizar en el initialize argumentos de palabras clave. Alternativamente, pasaré el original. nodos y bordes a partir de nuestros datos de entrada y crear un rango desde el DSatur como nuestra inicialización para los colores.

model.C = pyo.Set(initialize=range(len(dsatur.C)))  # Colors
model.N = pyo.Set(initialize=nodes) # Nodes
model.E = pyo.Set(initialize=edges]) # Edges

A continuación, creamos una instancia de nuestras variables de decisión.

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

Y luego nuestras limitaciones.

# Fill every node with some color
def fill_cstr(model, i):
return sum(model.x[i, :]) == 1

# Do not repeat colors on edges and indicator that color is used
def edge_cstr(model, i, j, c):
return model.x[i, c] + model.x[j, c] <= model.y[c]

# Break symmetry by setting a preference order (not required)
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)

Puede intentar incluir otras restricciones que rompan la simetría y ver qué funciona mejor con el solucionador disponible. En algunos experimentos que realicé, incluir un orden de preferencia utilizando el total de nodos asignados a un color determinado ha sido peor que ignorarlo. Posiblemente debido a las estrategias nativas de ruptura de simetría del solucionador.

# Break symmetry by setting a preference order with total assignments
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])

Por fin, el objetivo…

# Total number of colors used
def obj(model):
return sum(model.y[:])

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

¡Y nuestro modelo está listo para ser resuelto! Para hacer eso estoy usando el solucionador persistente HiGHS, que está disponible en piomo En caso espía también está instalado en su entorno Python.

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

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

Solución de programación entera para colorear gráficos para una instancia de 32 nodos. (Imagen del autor).