Performing DFS in a graph through constraints
I have considered a weighted graph G(V,E). I need to find the shortest path between two nodes by storing the route in a decision variable x[i,j] which is equal to 1, if the edge (i,j) is traversed otherwise 0. I need to create a binary decision variable y[i,j] which should be equal to 1 if i is connected to j. Can you tell me how to do it.
-
Official comment
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 why not try our AI Gurobot?. -
Hi Arun,
Did you find a way to solve your problem in Gurobi? I am trying something similar so it would help if you can share.
Thanks
0 -
From your description, this really sounds like a network flow model. What you would do is to model this as a digraph, i.e., with directed arcs. So, if you have an edge e=(i,j) you would introduce two arcs a=(i,j) and a'=(j,i) to the arc set A. Then, you use one binary variable for each arc: x[i,j] = 1 if that arc is used, x[i,j] = 0 if it is not used. Now, as constraints, you need the flow conservation constraints. This means, for every node j you formulate
sum{i: (i,j) in A} x[i,j] - sum{k: (j,k) in A} x[j,k] = 0Moreover, for your given source node s and your target node t you have to change the rhs of this flow conservation constraint such that the source becomes a source of 1 unit of flow and the target becomes the sink of 1 unit of flow. Hence for j=s and j=t, the flow conservation constraints would be
sum{i: (i,s) in A} x[i,s] - sum{k: (s,k) in A} x[s,k] = -1
sum{i: (i,t) in A} x[i,t] - sum{k: (t,k) in A} x[t,k] = 1Now, the only thing that is left is the objective function. But this is easy: this is just the weighted sum of the x variables, with the weights being the distances. Hence, if the distance between i and j is c[i,j] (I guess that your problem is symmetric, so that c[i,j] = c[j,i]), then the objective funciton will be
min sum{(i,j) in A} c[i,j]*x[i,j]This should be it to model the shortest path problem.
Note, of course, that MIP is not the best way to solve shortest path problems. Those can easily be solved with graph algorithms like Dijkstra. Using a MIP solver is a bit overkill.
Regards,
Tobias
1 -
Hi Tobias,
Thank you for your response. I had done something similar but it either gives a value of 0 for the objective function or throws this error:
'MIP start from previous solve did not produce a new incumbent solution
MIP start from previous solve violates constraint R32 by 1.000000000'
I am not sure where the issue is because i am using a very basic example for now. Do we need to use Lazy constraints in such a scenario? I can send my code if required.
0 -
A MIP start is a starting solution that is checked at the beginning of a solve whether it is feasible. If so, it will be used as an incumbent solution to speed up the optimization process. This MIP start can come from two sources: either you have set it manually yourself, or you have solved this model before, then modified it, and are now solving the modified model. In the latter case Gurobi would keep the old solution and try it as a MIP start for the subsequent solve. It doesn't matter if this solution is no longer feasible, so this warning message can be ignored.
You can use the
model.write("mymodel.lp")call to write out the model in the LP file format. This is human readable, so you can inspect the model and check whether it is what you expect. If not, then you have a mistake in your model building code.
0
Post is closed for comments.
Comments
5 comments