Estoy tratando de arreglar algunas restricciones para el problema de coloreado de Graph usando networkx y gurobi. Para cada i ∈ V, definimos el siguiente conjunto de intervalos. Cada intervalo [l, u] ∈ Ii representa un posible par de color mínimo ly color máximo u para el conjunto de bordes incidentes en el vértice i. Además, para cada k∈K, representamos el conjunto de intervalos para el vértice i ∈ V que incluyen el color k por:

Intervals variable

Este es todo el código que escribí:

import networkx as nx
import gurobi as gb
from itertools import combinations, chain
import pygraphviz as pygv
import os
import matplotlib.pyplot as plt
from IPython.display import SVG, display

Creación del gráfico, agregando nodos y aristas y dos listas.

G = nx.Graph()
G.add_nodes_from ([0,1,2,3,4])
G.add_edge(0,1)
G.add_edge(0,2)
G.add_edge(0,3)
G.add_edge(0,4)
G.add_edge(1,2)
G.add_edge(1,3)
G.add_edge(2,4)
G.add_edge(3,4)
U = list(G.nodes)
K = G.number_of_edges()
Z = []

creando una lista con colores. Suponemos que K = {0, 1,. . . , K - 1} y K ≤ | E |

def nrofCol():
    Z.clear()
    z = 0
    while z < K - 1:
        Z.append(z)
        z = z+1
    return Z

Z = nrofCol()
Z

aquí estoy definiendo el valor del intervalo (l, u), creando dos listas con todos los colores.

u = []
l = []

for z in Z:
    u.append(Z[z])
    l.append(Z[z])

Seré una lista de tuplas

I = []
for z in Z:
    for u in range (z, len(Z)):
        I.append(tuple((z, u)))

agregar atributo de color a cada borde

for colored_arc in ((u,v,z) for u,v in G.edges() for z in Z):
    G[colored_arc[0]][colored_arc[1]][colored_arc[2]] = colored_arc

y agregó variables al modelo usando Gurobi:

Variable y

indices = []

for u,v in G.edges(): 
    for z in Z:
        indices.append((u,v,z))

x = mdic.addVars(indices, vtype = gb.GRB.BINARY)

indices2 = []

for u in G.nodes(): 
    for i in range(0,len(I)): 
        indices2.append(tuple((u,I[i])))

for u in U:
    y = mdic.addVars(indices2, vtype = gb.GRB.BINARY)

mdic.update()

Las restricciones son: Restricciones y función objetivo

Constraints 2a- Asegúrese de que cada borde tome exactamente un color

for u,v in G.edges():

        mdic.addConstr(x.sum(u,v) == 1, name='one_color')

mdic.update()

2b: elija exactamente un intervalo (del conjunto de intervalos elegibles) para cada vértice.

for u in U:       
    mdic.addConstr(y.sum(u) == 1, name='used')

mdic.update()

2c- Garantizar que no solo los bordes adyacentes tomen diferentes colores, sino que también los bordes que inciden en un vértice toman colores del conjunto de colores incluido en el intervalo elegido para ese vértice

for u in U:
    for z in Z: 
        mdic.addConstr((x.sum(u,'*',z) + x.sum('*',u,z)) <= y.sum(u,I), name='different_colors')

mdic.update()

función objetiv

expr=0
for u in U:
    for i in range(0,len(I)):
        a = [i[1] for i in I][i]
        b = [i[0] for i in I][i]
        expr += (a - b - G.degree[u] + 1) * y[u,I[i]]
mdic.setObjective(expr, gb.GRB.MINIMIZE)

mdic.update()
mdic.optimize()

Utilizando este código, el modelo no es factible. Sé que la variable x y las restricciones 2a se definen de la manera correcta. No estoy seguro acerca de la variable y, otras restricciones y la función objetivo. ¿Cómo puedo cambiar esto