最短路径 LP 公式：反向链接取值 1

Question

我正在尝试使用 python 中的 PuLP 包实现最短路径问题的 ILP 公式。输入是使用 NetworkX 包生成的图形。

import networkx as nx
import pulp
import random
import matplotlib.pyplot as plt

g = nx.to_directed(nx.barabasi_albert_graph(20, 2))
# nx.draw(g, with_labels=True)
# plt.show()
source = 0
target = 13

dict_d = {}
for i, j in g.edges:
    dict_d[i, j] = dict_d[j, i] = round(random.uniform(1.0, 20.0), 2)

nx.set_edge_attributes(g, dict_d, 'delay')

# instantiate
prob = pulp.LpProblem("Shortest Path Problem", pulp.LpMinimize)
cost = nx.get_edge_attributes(g, 'delay')

# binary variable to state a link is chosen or not
var_dict = {}
for (i, j) in g.edges:
    x = pulp.LpVariable("x_(%s_%s)" % (i,j), cat=pulp.LpBinary)
    var_dict[i, j] = x

# objective function
prob += pulp.lpSum([cost[i, j] * var_dict[i, j] for i, j in g.edges]), "Total Hop Count"

# constraints
for node in g.nodes:
    if node == source:
        prob += pulp.lpSum([var_dict[i, k] for i, k in g.edges if k == node]) - \
                pulp.lpSum([var_dict[k, j] for k, j in g.edges if k == node]) == 1
    elif node == target:
        prob += pulp.lpSum([var_dict[i, k] for i, k in g.edges if k == node]) - \
                pulp.lpSum([var_dict[k, j] for k, j in g.edges if k == node]) == -1
    else:
        prob += pulp.lpSum([var_dict[i, k] for i, k in g.edges if k == node]) - \
                pulp.lpSum([var_dict[k, j] for k, j in g.edges if k == node]) == 0

# solve
prob.solve(pulp.GUROBI_CMD(msg=0))

print(pulp.LpStatus[prob.status])
print(pulp.value(prob.objective))
print("The shortest path is ")
for link in g.edges:
    if var_dict[link].value() == 1.0:
        print(link, end=" ")

如果我使用无向图，则流约束守恒不起作用，因为反向边不存在于图中。

prob += pulp.lpSum([var_dict[i, k] for i, k in g.edges if k == node]) - \
                pulp.lpSum([var_dict[k, j] for k, j in g.edges if k == node]) == 1

另一方面，在使用有向图时，反向边的指示变量取值，导致输出

The shortest path is (1, 2) (2, 0) (13, 1)

当输出应该是 (0,2) (2,1) (1,13)

所以我的问题有两个方面：

对于最短路径问题，是否有更好的 LP 公式表示可以完全避免此问题？
否则，如何获得有意义的路径作为输出？阻止反向弧取值？从我现在得到的输出中以某种方式获取路径？

Answer 1

If I use an undirected graph, the conservation of flow constraint does not work since the reverse edge is not present in the graph.

这不是真的：我用 prob.writeLP('eyes.lp') 检查平衡约束，似乎反向边缘存在。

On the other hand, while using directed graphs, the indicator variables of the reverse edge takes on values, leading to output
The shortest path is (1, 2) (2, 0) (13, 1)
when output should be (0,2) (2,1) (1,13)

这里的问题是源和目标约束的符号颠倒了：请注意，您的解决方案是从目标到源而不是从源到目标。如果您更改标志，它将正常工作：

# constraints
for node in g.nodes:
    rhs = 0
    if node == source:
        rhs = -1
    elif node == target:
        rhs = 1
    prob += pulp.lpSum([var_dict[i, k] for i, k in g.edges if k == node]) - \
            pulp.lpSum([var_dict[k, j] for k, j in g.edges if k == node]) == rhs

Is there a better representation of the LP formulation for the shortest path problem that avoids this problem altogether?

LP 公式正确。

Failing that, how to get a meaningful path as output? Stop the reverse arcs from taking on values? Get a path somehow from the output I am getting now?

修复标志应该可以正常工作。

最短路径 LP 公式：反向链接取值 1

Shortest path LP formulation : reverse links taking on value 1

python-3.x

shortest-path

linear-programming

pulp