图形着色，列表索引超出范围

Question

我正在尝试使用 networkx 创建一个带有与边关联的颜色的图形。每条边应具有所有颜色，但只会选择一种颜色。

Z = [0, 1, 2, 3, 4, 5, 6]
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

其中 u,v 是节点，z 是颜色。这是结果

for u,v in G.edges():
    for z in Z:
         print(G[u][v][z])

 (1, 2, 0)
 (1, 2, 1)
 (1, 2, 2)
 (1, 2, 3)
 (1, 2, 4)
 (1, 2, 5)
 (1, 2, 6)
 .....

现在我正在创建一个二进制变量（使用 gurobi），其中 1 是与每个边的正确颜色关联的值，所有其他颜色的值为 0。

 mdic = gb.Model()
 for u,v in G.edges():
      for z in Z:
           x = mdic.addVars(obj=[G[u][v][z]], ub = 1.0, vtype=gb.GRB.BINARY, name='x')

但这是错误：

IndexError                                Traceback (most recent call last)
<ipython-input-24-be25e6af1ffe> in <module>()
  5 for u,v in G.edges():
  6     for z in Z:
----> 7         x = mdic.addVars(obj=[G[u][v][z]], ub = 1.0, vtype=gb.GRB.BINARY, name='x')
  8 
  9 # decision variables s i and S i for i ∈ V to represent the minimum and maximum color in the set of colors

model.pxi in gurobipy.Model.addVars (../../src/python/gurobipy.c:80144)()

model.pxi in gurobipy.__listify.__init__ (../../src/python/gurobipy.c:50924)()

IndexError: list index out of range

Answer 1

使用 mdic.addVar(...) 而不是 mdic.addVars(...) 创建单个决策变量。函数 addVars 需要根据 http://www.gurobi.com/documentation/8.0/refman/py_model_addvars.html 的索引列表，您没有提供。因此你得到 IndexError。您可以将变量存储在列表中以在优化模型后获取它们的值。

# n: number of nodes
x = [[[None] * len(Z)] * (n+1)] * (n+1)

for u,v in G.edges():
    for z in Z:
        x[u][v][z] = mdic.addVar(vtype = gb.GRB.BINARY)

mdic.update()

# add constraints using the variables in x...
# add objective function...

mdic.optimize()

# get results using x[u][v][z].getAttr(GRB.Attr.x)

使用 addVars 的替代方法

indices = []

for u,v in G.edges(): 
    for z in Z:
        indices.append((u,v,z))

x = mdic.addVars(indices, vtype = gb.GRB.BINARY)

图形着色，列表索引超出范围

Graph coloring, list index out of range

python

networkx

gurobi

使用 addVars 的替代方法