2
$\begingroup$

I am working on a graph problem and want to find some link-disjoint paths between given node pairs. I was wondering if there is an efficient way to achieve this in CP. I checked OR-Tools (routing and network flows sections) but could not model this problem.

The problem is simple. For example in the graph below, I want to find two diverse paths between 1 and 8 (green paths) and 3 diverse paths from 2 to 5, 6, and 8 (blue paths). Example of the required paths

Improve this question
$\endgroup$
3
  • $\begingroup$ Welcome to ORSE. Maybe this post would be interesting. :) $\endgroup$
    – A.Omidi
    Jun 27, 2022 at 4:39
  • $\begingroup$ Are you interested in solutions using integer programming, or only CP solutions? $\endgroup$
    – prubin ♦
    Jun 27, 2022 at 15:38
  • $\begingroup$ @prubin I am familiar with ILP formulation of this problem. It is not quite easy to force diversity in integer programming (requires a huge number of constraints to make sure that each link is used at most once in each set of diverse paths in addition to loop elimination constraints and comes with scalability issues). I have even worked on decomposition techniques like Dantzig-Wolfe for this problem. I am more interested in CP right now. $\endgroup$
    – hmd.pouya
    Jun 27, 2022 at 16:00

1 Answer 1

Reset to default
2
$\begingroup$

I not complete sure what you mean about "link disjoint paths". Does that mean two paths cannot share any edges or that they should not be identical (in which case they are not very diverse)?

If you would like a set of different (short) paths between two nodes, which may have edges in common, you could use a solver for the $K$-shortest path. You can e.g. use Yen's algorithm for that.

If the paths should be completely different (no common edges) then you could solve a series of shortest path problems where in each iteration, you remove the edges used in paths in previous iterations.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Link disjoint means the paths have no common links/edges. This is an optimization problem and yes a greedy algorithm as you described returns a solution, maybe a good one. However, I am looking for the optimal solution. It is easy to see that choosing the wrong path or starting from the wrong place will make the problem infeasible. The first step here is to answer the feasibility problem i.e., whether there is a set of paths such that the diversity constraints are satisfied. If yes, then what is the best set? Maybe the set with overall shortest length. $\endgroup$
    – hmd.pouya
    Jun 27, 2022 at 12:52
  • $\begingroup$ @hmd.pouya Is the objective to find as many edge disjoint paths as possible or to find say $K$ paths for a fixed $K$? If the latter is the case, when is a set of $K$ paths better than a different set of $K$ paths? If you want a best set of "diverse paths" you need to define an objective function that can assign a score to a set so that two sets can be compared. $\endgroup$
    – Sune
    Jun 27, 2022 at 14:10
  • $\begingroup$ Everything is known including number of diverse paths and source-destination for all paths (just like the simple example in the question). As I mentioned before, the first step is to solve the feasibility problem which has no objective function. $\endgroup$
    – hmd.pouya
    Jun 27, 2022 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.