Shortest Path Problem infeasible

I 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 < n-1:
                cost = random.randint(down, up)
                src = i * m + j
                dst = (i + 1) * m + j
                graph.add_edge(src, dst, cost=cost)
            if j < m-1:
                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?

Riley Clement

Gurobi Staff

July 06, 2023 00:29 Edited

Hi Jade,

Your last node has index t-1, 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 t-1 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 t-1 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

Gleb Sibul

July 07, 2023 15:42

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?

July 08, 2023 03:22

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

Shortest Path Problem infeasible

Comments

Didn't find what you were looking for?