具有间隔 Gurobi 约束的图形着色

Question

我正在尝试使用 networkx 和 gurobi 解决图形着色问题的一些限制。对于每个 i ∈ V，我们定义了以下一组区间。每个区间 [l,u] ∈ Ii 表示入射到顶点 i 的一组边的可能的最小颜色 l 和最大颜色 u 对。此外，对于每个 k∈K ，我们表示顶点 i ∈ V 的区间集，其中包括颜色 k ：

Intervals variable

这是我写的所有代码：

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

创建图，添加节点和边以及两个列表。

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

正在创建一个包含颜色的列表。我们假设 K = {0, 1, . . . , K − 1} 且 K ≤ |E|

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

Z = nrofCol()
Z

这里我定义了区间 (l,u) 的值，创建了两个包含所有颜色的列表。

u = []
l = []

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

我将是一个元组列表

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

为每条边添加颜色属性

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 向模型添加变量：

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

约束是： Contraints and objective function

约束 2a- 确保每条边只采用一种颜色

for u,v in G.edges():

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

mdic.update()

2b- 为每个顶点恰好选择一个区间（从一组符合条件的区间）。

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

mdic.update()

2c-保证不仅相邻的边采用不同的颜色，而且入射到一个顶点的边也采用为该顶点选择的间隔中包含的颜色集中的颜色

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

objective 函数

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

使用此代码，模型不可行。我知道变量 x 和约束 2a 是以正确的方式定义的。我不确定变量 y、其他约束和 objective 函数。我该如何更改？

Answer 1

应该为每个节点分别定义间隔列表I[i]:

I = []
for i in G.nodes():
    Ii = []
    for z in Z:
        for u in range (z, len(Z)):
            if u - z >= G.degree(i) - 1:
                Ii.append(tuple((z, u)))
    I.apppend(Ii)

I 的用法必须改为如下形式：

indices2 = []

for i in G.nodes(): 
    for interval in I[i]: 
        indices2.append(tuple((i,interval)))

变量 y 现在应该只创建一次：

y = mdic.addVars(indices2, vtype = gb.GRB.BINARY)

约束 2c 也必须更改，因为在您的屏幕截图中，正确的总和仅迭代 I:

for u in U:
    for z in Z:

        y_sum = 0
        for z1,z2 in I[u]:
            if z1 <= z and z <= z2:
                y_sum += y[u,(z1,z2)]

        mdic.addConstr((x.sum(u,'*',z) + x.sum('*',u,z)) <= y_sum, name='different_colors')

具有间隔 Gurobi 约束的图形着色

Graph coloring with intervals Gurobi constraints

python

graph-theory

networkx

gurobi