Skip to main content

Performing DFS in a graph through constraints

Comments

4 comments

  • Upasana Chakraborty
    Gurobi-versary
    Conversationalist
    First Question

    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
  • Tobias Achterberg
    Gurobi Staff Gurobi Staff

    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] = 0

    Moreover, 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] = 1

    Now, 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
  • Upasana Chakraborty
    Gurobi-versary
    Conversationalist
    First Question

    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
  • Tobias Achterberg
    Gurobi Staff Gurobi Staff

    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

Please sign in to leave a comment.