I have a particular shortest path problem in which the nodes are partitioned into sets S_i. The path should contain at most one node for each S_i, in other words the nodes of each set are mutually exclusive.
Obviously, I could formulate it as an ILP but the complexity would be not polynomial. Is there a way to adapt some of the classical shortest path algorithms (Dijkstra, Bellman-Ford, etc.), so that the complexity stays polynomial?
Thanks!
Thanks for the suggestion, but I would prefer an exact method, not a heuristic...
We discussed your problem today on our working group meeting. One of my PhDs, Eric Yuan Zhi, pointed out that yours seems to be a generalization of the shortest path problem with forbidden pairs (in case each cluster has exactly two nodes in it), and that problem is already known to be hard: http://arxiv.org/pdf/1111.3996.pdf
You confirm what I was fearing... but thank you, your link is very interesting. If you do research on this topic, I'll be glad to exchage ideas.
Many regards
I do research in general mixed-integer linear and nonlinear optimization and its application to real-world problems. If this is of any help for you, I'm always open for sharing ideas.
Here are some possibilities.
(1) Don't count out the ILP formulation. The mutual exclusion with sets provides a number of constraints, so a branch-and-bound scheme might be fairly effective, that is, solving relaxations might give a solution without need for much fathoming.
(2) If by any chance the graph corresponds to a physical layout (a map, say) and sets are determined by proximity, then you might get viable results by using a standard shortest path method, once you make path distances within sets equal to infinity.
(3) Possibly a recursion approach will work well (at the expense of considerable memory, for caching intermediate results). Suppose we want to go from v1, in set S1, to v2 in set S2. The idea is that you have a function
f(v1, v2, avoid_list)
denoting shortest distance from v1 to v2 avoiding everything on the avoid list (initially empty). The recursive definition is that it is the min of the direct distance between them (assuming it is finite) and all sums of the form
f(v1,v3,(S2)) + f(v3,v2,(S1))
where v3 is not in S1 or S2.
Depending on how large is the node set and how many tend to be in common subsets, this might be a reasonable approach.
- Badges
- Science topic
- Similar topics
- Computer Science
- Data Mining