I'm trying to fix some constraints for the Graph coloring problem using networkx and gurobi. This is all the code that i wrote:
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
Creation of the graph, adding nodes and edges and two lists.
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 = []
creating a list with colors. We assume that K = {0, 1, . . . , K − 1} and K ≤ |E|
def nrofCol():
Z.clear()
z = 0
while z < K - 1:
Z.append(z)
z = z+1
return Z
Z = nrofCol()
adding color attribute to each edge
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
and added variables to the model using 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()
And then the constraints:
# 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) <= 1, name='different_color')
mdic.update()
# 1b- Guarantee that every edge takes exactly one color
for u,v in G.edges():
mdic.addConstr(x.sum(u,v) == 1, name='one_color')
mdic.update()
# 1c- Enforce Si to be greater than or equal to the max 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='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()
where Z is the set of available colors.
# 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()
Constraints
The first one is the objective function, 1a to 1d are the constraints and the others are ub and lb.