CODEWITHSUNDEEP
python-3.xshortest-pathlinear-programmingpulp
Niloy Saha
Niloy Saha

Reputation: 484

Shortest path LP formulation : reverse links taking on value 1

I am trying to implement an ILP formulation of the shortest path problem using the PuLP package in python. The input is a graph generated using the NetworkX package. 

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=" ")

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 += 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

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)

So my question is two-pronged:

  1. Is there a better representation of the LP formulation for the shortest path problem that avoids this problem altogether?
  2. 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?

Upvotes: 1

Views: 1647

Answers (1)

Ioannis
Ioannis

Reputation: 5408

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

This is not true: I used prob.writeLP('eyes.lp') to check the balance constraints, and it seems that the reverse edges are present.

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)

The problem here is that the signs of the source and the target constraints are flipped: notice that your solution goes from target to source instead of source to target. If you change the signs, it will work correctly:

# 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?

The LP formulation is correct.

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?

Fixing the signs should make it work.

Upvotes: 2

Related Questions