# Finding Diverse Paths using Constraint Programming

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).

• Welcome to ORSE. Maybe this post would be interesting. :) Jun 27, 2022 at 4:39
• Are you interested in solutions using integer programming, or only CP solutions?
– prubin
Jun 27, 2022 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. Jun 27, 2022 at 16:00

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.
• @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.