Shortest Path Problem infeasible
AnsweredI am solving the Shortest Path Problem on a generated n by m lattice directed graph with positive edge costs using Gurobi.
The code is as follows:
import networkx as nx
import gurobipy as gp
from gurobipy import GRB
import random
n = 3
m = 3
down = 1
up = 10
s = 0
def create_graph(n, m, up, down):
graph = nx.DiGraph()
for i in range(n):
for j in range(m):
node_id = i * m + j
graph.add_node(node_id)
for i in range(n):
for j in range(m):
if i < n1:
cost = random.randint(down, up)
src = i * m + j
dst = (i + 1) * m + j
graph.add_edge(src, dst, cost=cost)
if j < m1:
cost = random.randint(down, up)
src = i * m + j
dst = i * m + (j + 1)
graph.add_edge(src, dst, cost=cost)
return graph
graph = create_graph(n, m, up, down)
t = len(list(graph.nodes))
model = gp.Model()
x = model.addVars(graph.edges, vtype=GRB.BINARY)
model.setObjective(gp.quicksum(graph.edges[i, j]['cost'] * x[i, j] for i, j in graph.edges), GRB.MINIMIZE)
model.addConstr(gp.quicksum(x[j, s] for j in graph.predecessors(s))  gp.quicksum(x[s, j] for j in graph.successors(s)) == 1)
model.addConstrs(gp.quicksum(x[j, i] for j in graph.predecessors(i))  gp.quicksum(x[i, j] for j in graph.successors(i)) == 0 for i in graph.nodes if i not in {s, t})
model.addConstr(gp.quicksum(x[j, t  1] for j in graph.predecessors(t  1))  gp.quicksum(x[t  1, j] for j in graph.successors(t  1)) == 1)
model.optimize()
The output of the model shows it is infeasible. Where might be the problem?

Hi Jade,
Your last node has index t1, which you are aware of based off the last constraint, however your check in the flow conservation constraints is:
if i not in {s, t}
If you replace t with t1 you will get a valid solution.
Also, since you know
gp.quicksum(x[t  1, j] for j in graph.successors(t  1)
will equal 0, on account of node t1 having no successors you can remove this from the constraint.
Likewise, you do not need
gp.quicksum(x[j, s] for j in graph.predecessors(s))
in your first constraint.
 Riley
0 
Thank you very much! Is it possible to make this problem stochastic by considering k samples of edge costs and finding CVAR of the objective for some alpha?
0 
Hi Jade,
Apologies, I have no idea what CVAR and alpha are referring to, but stochastic network flow problems can certainly be modeled and solved. See this paper, for example
Stochastic flow networks via multiple paths under time threshold and budget constraint Riley
0
Please sign in to leave a comment.
Comments
3 comments