Estou tentando corrigir algumas restrições para o problema de coloração do Graph usando networkx e gurobi. Para cada iV, definimos o seguinte conjunto de intervalos. Cada intervalo [l, u] ∈i representa um possível par de cor mínima le cor máxima u para o conjunto de arestas incidentes no vértice i. Além disso, para cada k∈K, representamos o conjunto de intervalos para o vértice i ∈ V que incluem a cor k por:

Intervals variable

Este é todo o código que escrevi:

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

Criação do gráfico, adicionando nós e arestas e duas lista

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 = []

Criando uma lista com cores. Assumimos que K = {0, 1,. . . , K - 1} e K ≤ | E |

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

Z = nrofCol()
Z

aqui estou definindo o valor do intervalo (l, u), criando duas listas com todas as core

u = []
l = []

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

Será uma lista de tupla

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

adicionar atributo de cor a cada borda

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

e adicionamos variáveis ao 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()

As restrições são:estrições e função objeti

Restrições 2a- Verifique se cada aresta tem exatamente uma cor

for u,v in G.edges():

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

mdic.update()

2b- Escolha exatamente um intervalo (do conjunto de intervalos elegíveis) para cada vértic

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

mdic.update()

2c- Garanta que não apenas as arestas adjacentes tenham cores diferentes, mas também as arestas incidentes em um vértice recebam cores do conjunto de cores incluído no intervalo escolhido para esse 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()

função 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()

Usando esse código, o modelo é inviável. Eu sei que a variável xe as restrições 2a são definidas da maneira correta. Não tenho certeza sobre a variável y, outras restrições e a função objetivo. Como eu posso mudar isso