带间隔 Gurobi 约束的图形着色

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

间隔变量 https://i.stack.imgur.com/XctNo.jpg

这是我写的所有代码：

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 将变量添加到模型中：

变量y https://i.stack.imgur.com/yK5Ci.jpg

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

限制条件是：约束和目标函数 https://i.stack.imgur.com/Dygzs.jpg

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

目标函数

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、其他约束和目标函数。我怎样才能改变这个？

区间列表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')