带有间隔Gurobi约束的图形着色 [英] Graph coloring with intervals Gurobi constraints

问题描述

我正在尝试使用networkx和gurobi来解决Graph着色问题的一些约束.对于每个i∈V，我们定义以下间隔集.每个间隔[l，u]∈Ii代表入射到顶点i的一组边的最小颜色l和最大颜色u的可能对.另外，对于每个k∈K，我们用以下公式表示顶点i∈V的间隔集合，其中包括颜色k:

I'm trying to fix some constraints for the Graph coloring problem using networkx and gurobi. For each i ∈ V, we define the following set of intervals. Each interval [l,u] ∈ Ii represents a possible pair of minimum color l and maximum color u for the set of edges incident to vertex i. Also, for each k∈K , we represent the set of intervals for vertex i ∈ V which include color k by :

时间间隔变量

这是我编写的所有代码:

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

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

在这里，我定义间隔(l，u)的值，创建两个具有所有颜色的列表.

here i'm defining the value of the interval (l,u), creating two list with all the colors.

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

为每个边缘添加颜色属性

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:

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

约束是: 约束和目标函数

约束2a-确保每个边缘仅采用一种颜色

Constraints 2a- Ensure that each edge takes exactly one color

for u,v in G.edges():

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

mdic.update()

2b-为每个顶点精确选择一个间隔(从合格间隔中选择).

2b- Choose exactly one interval (from the set of eligible intervals) for each vertex.

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

mdic.update()

2c-确保不仅相邻的边缘采用不同的颜色，而且入射到顶点的边缘也从该顶点选择的间隔中包括的颜色集中获取颜色

2c- Guarantee that not only adjacent edges take different colors, but also edges incident to a vertex take colors from the set of colors included in the interval chosen for that vertex

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，其他约束和目标函数.我该如何更改?

Using this code, the model is unfeasible. I know that variable x and constraints 2a are defined in the right way. I'm not sure about variable y, other constraints and the objective function. How can i change this?

推荐答案

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

The interval list I[i] should be defined for each node separately:

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的用法更改为以下内容:

The usage of I must then be changed to something like this:

indices2 = []

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

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

Variables y should now only be created once:

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

约束2c也必须更改，因为在屏幕快照中，正确的总和仅在I的子集上进行迭代:

Constraint 2c must also be changed because in your screenshot the right sum iterates only over a subset of 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约束的图形着色的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！