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

Question

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

S >= quicksum(uij for j in N) for every i in N

我的密码是

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

问题是我得到 Key Error (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)))

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