2

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

Laurent Perron
  • 2,690
  • 1
  • 6
  • 18
hmd.pouya
  • 21
  • 2
  • Welcome to ORSE. Maybe this post would be interesting. :) – A.Omidi Jun 27 '22 at 04:39
  • Are you interested in solutions using integer programming, or only CP solutions? – prubin Jun 27 '22 at 15:38
  • @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. – hmd.pouya Jun 27 '22 at 16:00

1 Answers1

2

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.

Sune
  • 6,457
  • 2
  • 17
  • 31
  • 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. – hmd.pouya Jun 27 '22 at 12:52
  • @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. – Sune Jun 27 '22 at 14:10
  • 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. – hmd.pouya Jun 27 '22 at 15:05