python - 尝试对图中节点组合的总和进行编码，以使用 quicksum 进行 gurobi 优化

Question

我正在尝试使用 gurobi 和 networkx 将其编码到 python 中，

S >= quicksum(uij for j in N) 对于 N 中的每个 i

我的代码是

import gurobipy as grb
import networkx as nx

g = nx.Graph()
g.add_edges_from(edges)

for i in g.nodes_iter():
     m.addConstr(S >= grb.quicksum(u[i,j] for j in g.nodes_iter()))

问题是我得到关键错误（1,1），这是有道理的，因为我没有优势（1,1）

但我确实想为节点中的每个 i 求和，即连接到特定节点 i 的所有 j 的所有 uij 的总和。

这不是度数问题，它实际上是对连通分量求和，因此如果 i 和 j 之间存在路径，则 uij 为 1。我已将此编码为关键节点检测问题。

请帮忙！谢谢！

Answer 1

您希望总和刚好超过图中的节点。networkx 有一种方法neighbors_iter可以做到这一点

for i in g.nodes_iter():
 m.addConstr(S >= grb.quicksum(u[i,j] for j in g.neighbors_iter(i)))

在任何情况下，您都应该避免遍历所有节点对，除非您只使用非常密集的图。