Skip to main content

Shortest Path Problem infeasible

Answered

Comments

3 comments

  • Riley Clement
    Gurobi Staff Gurobi Staff

    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

    0
  • Gleb Sibul
    Gurobi-versary
    First Comment
    First Question

    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
  • Riley Clement
    Gurobi Staff Gurobi Staff

    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.