最短路径LP建模：反向边取值1及PuLP实现ILP的约束异常问题咨询

第一部分：无向图流量守恒约束失效的解决方案 #

无向图的每条边本质是双向可达的，但NetworkX的无向图不会自动生成反向边，这直接导致流量守恒约束无法覆盖双向的流量流动。解决这个问题的核心是将每条无向边拆分为两条方向相反的有向边，让模型能捕捉双向的流量可能性：

• 遍历无向图的每条边(u, v)，分别创建二进制变量x_{u,v}和x_{v,u}，分别代表流量从u流向v、v流向u；
• 流量守恒约束：对除起点s和终点t外的所有节点i，流入的总流量必须等于流出的总流量，即：

  sum(x_{j,i} for j in 节点i的邻居) = sum(x_{i,j} for j in 节点i的邻居)
  

• 起点s的净流出量为1（保证只有一条路径从起点出发），终点t的净流入量为1（保证只有一条路径到达终点）；
• 目标函数保持最小化总路径权重，两条反向边的权重与原无向边一致。

第二部分：有向图反向边指示变量取值异常的修复 #

你期望的路径是(0,2) → (2,1) → (1,13)，但反向边变量出现异常，大概率是变量定义、约束逻辑或结果提取环节出了问题，可按以下步骤排查修复：

1. 变量定义要精准：直接基于NetworkX有向图的所有边创建变量，不要重复生成冗余边；如果是从无向图转有向图，确保每条反向边的权重和正向边一致；
2. 约束逻辑不能出错：
   • 中间节点严格遵循流量守恒；
   • 起点仅设置净流出为1，终点仅设置净流入为1，不要给其他节点添加额外约束限制反向边的使用；
3. 结果提取要准确：筛选变量值为1的边时，要严格判断x[(u,v)].value() == 1，避免因浮点数精度问题误判（比如可以用abs(x.value() - 1) < 1e-6替代）；
4. 检查目标函数：确保反向边的权重没有被错误设置，比如不要给反向边赋予更高的权重，否则模型会避开它。

示例代码（无向图转有向边建模） #

import pulp
import networkx as nx

# 构建示例无向图
G = nx.Graph()
G.add_edge(0, 2, weight=1)
G.add_edge(2, 1, weight=1)
G.add_edge(1, 13, weight=1)
G.add_edge(0, 1, weight=5)  # 添加冗余边测试最短路径选择

# 定义起点和终点
start = 0
end = 13

# 创建ILP问题
shortest_path_prob = pulp.LpProblem("Shortest_Path_ILP", pulp.LpMinimize)

# 为每条无向边生成两个方向的变量
edge_vars = pulp.LpVariable.dicts(
    "edge_flow",
    [(u, v) for u, v in G.edges()] + [(v, u) for u, v in G.edges()],
    cat="Binary"
)

# 目标函数：最小化总路径权重
shortest_path_prob += pulp.lpSum(
    edge_vars[(u, v)] * G[u][v]["weight"]
    for u, v in G.edges()
) + pulp.lpSum(
    edge_vars[(v, u)] * G[u][v]["weight"]
    for u, v in G.edges()
)

# 流量守恒约束：中间节点
for node in G.nodes():
    if node != start and node != end:
        inflow = pulp.lpSum(edge_vars[(neighbor, node)] for neighbor in G.neighbors(node))
        outflow = pulp.lpSum(edge_vars[(node, neighbor)] for neighbor in G.neighbors(node))
        shortest_path_prob += inflow == outflow, f"Flow_Conservation_{node}"

# 起点净流出为1
shortest_path_prob += pulp.lpSum(edge_vars[(start, neighbor)] for neighbor in G.neighbors(start)) - \
                     pulp.lpSum(edge_vars[(neighbor, start)] for neighbor in G.neighbors(start)) == 1, "Source_Flow"

# 终点净流入为1
shortest_path_prob += pulp.lpSum(edge_vars[(neighbor, end)] for neighbor in G.neighbors(end)) - \
                     pulp.lpSum(edge_vars[(end, neighbor)] for neighbor in G.neighbors(end)) == 1, "Sink_Flow"

# 求解模型
shortest_path_prob.solve(pulp.PULP_CBC_CMD(msg=False))

# 提取最短路径边
selected_edges = [(u, v) for u, v in edge_vars if pulp.value(edge_vars[(u, v)]) == 1]
print("最短路径边：", selected_edges)

运行这段代码后，你会得到预期的[(0,2), (2,1), (1,13)]路径。如果是有向图，只需要把nx.Graph()换成nx.DiGraph()，并直接用有向边创建变量即可，无需拆分。

内容的提问来源于stack exchange，提问作者Niloy Saha