图形着色Gurobi约束 [英] Graph coloring Gurobi constraints

问题描述

我正在尝试使用networkx和gurobi来解决Graph着色问题的一些约束.这是我编写的所有代码:

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

创建带有颜色的列表.我们假设K = {0，1，，. . . ，K − 1}和K≤| E |

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

并使用Gurobi向模型添加变量:

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()

然后是约束:

# 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()

其中Z是可用颜色的集合.

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()

约束

第一个是目标函数，1a到1d是约束，其他是ub和lb.

The first one is the objective function, 1a to 1d are the constraints and the others are ub and lb.

推荐答案

假设您使用的是无向图，我发现了几个问题:

Assuming that you use an undirected graph, I found several problems:

约束(1a)确保相邻的边缘具有不同的颜色.但是，使用此约束的实现可能会发生传入和传出边缘具有相同颜色的情况.例如，边缘{1,3}和{3,5}可以具有相同的颜色.那是因为您分别处理传入和传出边缘.作为解决方案，您可以将循环合并为一个:

Constraint (1a) in your screenshot ensures that adjacent edges have different colors. However, with your implementation of this constraint it could happen that an incoming and an outgoing edge have the same color. E.g., edge {1,3} and {3,5} could have the same color. That's because you handle incoming and outgoing edges separately. As a solution, your could combine your loops into one:

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

约束(1c)也仅考虑实现中的传出边缘.例如，将不会分配S_i[5]，因为它仅具有传入边.这应该起作用:

Constraint (1c) also considers only outgoing edges in your implementation. E.g., S_i[5] would not be assigned because it has only incoming edges. This should work:

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

约束(1d)也是如此.更进一步，addConstr行不在循环中，但这可能只是格式错误:

The same goes for constraint (1d). Morover the addConstr line is outside of the loop, but this could just be a formatting error:

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

这篇关于图形着色Gurobi约束的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！