Shortest Path Problem LP formulation

回答済み

Elias Ødegaard

2022年04月22日 08:50

• 
• 
• 

Hello, 

I am trying to formulate a basic Shortest Path Problem as an LP formulation. It is functioning as planned, but I am having a hard time adding the "conservation of flow"-constraints (4 in the picture) in a generic way.  As of now, they are added one by one as presented below:

m.addConstr(x[0,1]-x[1,2]-x[1,3] == 0) 
m.addConstr(x[0,2]+x[1,2]-x[2,3]-x[2,4]-x[2,5] == 0 )
m.addConstr(x[1,3]+x[2,3]-x[3,4]-x[3,5] == 0 )
m.addConstr(x[2,4]+x[3,4]-x[4,5]-x[4,6]-x[4,7] == 0 )
m.addConstr(x[2,5]+ x[3,5] + x[4,5]- x[5,6]-x[5,7] == 0)
m.addConstr(x[3,6]+x[4,6]-x[6,7] == 0)

With a more generic way of adding these constraints, the model would be much easier to expand and use on larger problems.

best regards,

Elias

1

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2025年11月16日 23:39

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
• 

  Jonasz Staszek

  • Community Moderator

  2022年04月22日 12:40 編集済み

  • 
  • 
  • 

  Hi Elias,

  you could for example use NetworkX to construct your graph and then simply iterate over its nodes and their respective predecessors and successors to build your constraints. For your toy example, you could have:

  import networkx as nx
  import gurobipy as gp
  G = nx.DiGraph()
  
  # adding directed edges inferred from the example (NetworkX adds nodes automatically)
  G.add_edges_from([(0,1), (1,2), (1,3), (0,2), (2,3), (2,4), (2,5), (3,4), (3,5), (3,6), (4,5), (4,6), (4,7), (5,6), (5,7), (6,7)])
  
  # defining the model and variables
  m = gp.Model()
  x = gp.tupledict()
  for (v1, v2) in G.edges:
      x[v1, v2] = m.addVar(vtype="B", name=f"x_{v1}_{v2}")
      
  
  # adding flow conservation constraints
  for v in G.nodes:
      # we need to skip the source (0) and the sink (7)
      if v not in [0,7]:
          # we collect the predecessor variables
          expr1 = gp.quicksum(x[i,v] for i in G.predecessors(v))
          
          # we collect the successor variables 
          expr2 = gp.quicksum(x[v, j] for j in G.successors(v))
          
          # we add the constraint
          m.addLConstr(expr1 - expr2 == 0)

  Obviously, NetworkX does not require constructing the graph manually, as I did in the example above. You will find numerous ways to import a graph into NetworkX in the documentation. 

  Hope this helps.

  Best regards
  Jonasz

  1
• 

  Elias Ødegaard

  2022年04月25日 07:37

  • 
  • 
  • 

  Thank you, Jonasz! 

  This was very helpful:)

  Elias

  1

投稿コメントは受け付けていません。