Gráfico para colorear restricciones de Gurobi.

Estoy tratando de arreglar algunas restricciones para el problema de coloreado de Graph usando networkx y gurobi. 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 ([1,2,3,4,5]) G.add_edge(1,2) G.add_edge(1,3) G.add_edge(1,4) G.add_edge(1,5) G.add_edge(2,3) G.add_edge(2,4) G.add_edge(3,5) G.add_edge(4,5) U = list(G.nodes) K = G.number_of_edges() Z = [] 

Creando una lista con los 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() 

añadiendo 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 añadidas variables al modelo usando Gurobi:

     mdic = gb.Model() indices = [] for u,v in G.edges(): for z in Z: indices.append((u,v,z)) # binary variable that assing 1.0 to the color associated to the edge and 0.0 to the others x = mdic.addVars(indices, vtype = gb.GRB.BINARY) # decision variable S i for i ∈ V represents the maximum color in the set of colors assigned to edges incident to vertex i S_i = [] for u in U: S_i.append(mdic.addVar(vtype=gb.GRB.CONTINUOUS, lb = G.degree[u] - 1, ub = K - 1, \ name = 'max_color'+str(u))) # decision variable s_i for i ∈ V represents the minimum color in the set of colors assigned to edges incident to vertex i s_i = [] for u in U: s_i.append(mdic.addVar(vtype=gb.GRB.CONTINUOUS, lb = 0.0, ub = K - G.degree[u], \ name='min_color'+str(u))) mdic.update() 

    Y luego las restricciones:

     # 1a- Guarantee that adjacent edges take different colors for u in U: for z in Z: mdic.addConstr(x.sum(u,'*',z) <= 1, name='different_color') mdic.update() # 1a- Guarantee that adjacent edges take different colors for u in U: for z in Z: mdic.addConstr(x.sum('*',u,z) = expr, name='max') expr = 0 # 1d- Enforce si to be less than or equal to the min color assigned to the edges incident to vertex i expr = 0 for u,v in G.edges(): for z in Z: expr += z * x[u,v,z] mdic.addConstr(s_i[u] <= expr, name='min') expr = 0 mdic.update() 

    donde Z es el conjunto de colores disponibles.

     # objective function expr20=0 for u in U: expr20+=(S_i[u] - s_i[u] - G.degree[u] + 1) mdic.setObjective(expr20, gb.GRB.MINIMIZE) mdic.update() mdic.optimize() 

    Restricciones

    La primera es la función objective, 1a a 1d son las restricciones y las otras son ub y lb.

    Suponiendo que usa un gráfico no dirigido, encontré varios problemas:

    La restricción (1a) en su captura de pantalla garantiza que los bordes adyacentes tengan colores diferentes. Sin embargo, con su implementación de esta restricción, puede ocurrir que un borde entrante y otro saliente tengan el mismo color. Por ejemplo, el borde {1,3} y {3,5} podrían tener el mismo color. Esto se debe a que maneja los bordes entrantes y salientes por separado. Como solución, podrías combinar tus bucles en uno solo:

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

    La restricción (1c) también considera solo los bordes salientes en su implementación. Por ejemplo, S_i[5] no se asignaría porque solo tiene bordes entrantes. Esto debería funcionar:

     expr = 0 for u,v in G.edges(): for z in Z: expr += z * x[u,v,z] mdic.addConstr(S_i[u] >= expr, name='max') mdic.addConstr(S_i[v] >= expr, name='max') expr = 0 

    Lo mismo ocurre con la restricción (1d). Además, la línea addConstr está fuera del bucle, pero esto podría ser un error de formato:

     expr = 0 for u,v in G.edges(): for z in Z: expr += z * x[u,v,z] mdic.addConstr(s_i[u] <= expr, name='min') mdic.addConstr(s_i[v] <= expr, name='min') expr = 0