5
$\begingroup$

I recently got interested in the following variation of the shortest path problem. I've looked in the literature for days but I couldn't find any paper studying this problem. I'd like to ask if you have seen this problem (or any similar problem) before, and if you could point me to some relevant literature.

In a few words, the problem is as follows. We have a directed graph $G = (V, E)$. For each vertex $v \in V$ we have a set $S_v \in \mathbb R^m$ (say convex) and a point in it $x_v \in S_v$. The length of the edge $(u,v) \in E$ is, e.g., the Euclidean distance between $x_u$ and $x_v$. A path $P$ from source $s \in V$ to destination $d \in V$ is defined the usual way. The length of the path $P = (v_1=s, v_2, \ldots, v_{n-1}, v_n=d)$, on the other hand, is defined as the minimum w.r.t. the point locations $x_{v_1} \in S_{v_1}, \ldots, x_{v_n} \in S_{v_n}$ of the sum of the lengths of the edges $(v_1, v_2), \ldots, (v_{n-1}, v_n)$. Among all paths from $s$ to $d$, we seek one of minimum length.

This problem has the flavor of the "Euclidean shortest path" (see e.g. Sharir and Schorr, "On Shortest Paths in Polyhedral Spaces") which is common in robot navigation, but it has important differences. I've also seen shortest path problems with generalized arc lengths (see e.g. Frieze, "Minimum Paths in Directed Graphs"), but this problem formulation doesn't quite match the one above either.

Any thoughts/ideas?

$\endgroup$
  • $\begingroup$ You say that for each $v\in V$ you have a set $S_v$ and a point $x_v\in S_v$. That makes it sound as if there is a single fixed $x_v$ for each $v$. Later, when defining path length, it sounds as if $x_v$ is chosen differently for each path encountered. Which is correct? $\endgroup$ – prubin Nov 21 at 23:11
  • $\begingroup$ OK, I see what you mean. The second is correct: when defining the length of a path we are free to optimize over the position of the points $x_v$, hence as you say the location of the points $x_v$ depends on the path. I said that there is a single point per vertex since I'm interested in the single-source single-destination shortest path problem. Therefore I'm actually only interested in the location of the points $x_v$ that minimizes the length of the shortest path. $\endgroup$ – Tobia Marcucci Nov 22 at 1:27
  • $\begingroup$ Is the graph incomplete (meaning that you are not allowed to move directly from certain nodes to certain other nodes, but must pass through intervening nodes)? $\endgroup$ – prubin Nov 22 at 16:46
  • $\begingroup$ Yes, I'm not assuming the graph to be complete. $\endgroup$ – Tobia Marcucci Nov 22 at 17:12
  • $\begingroup$ Funny, something similar popped up here, where sets $S_v$ are line segments. $\endgroup$ – Kuifje Nov 25 at 19:37
4
$\begingroup$

To answer the original question, this is not a problem I have seen before. I upvoted Kuifje's answer, because while approximate it should be fairly computationally efficient if the discretization does not create too many points.

Another approach that I think would work would be a riff on Benders decomposition. It requires that the convex sets be polyhedral and given algebraically (either as sets of extreme points and extreme rays or as solutions to sets of linear inequalities). The master problem would be a mixed integer linear program that selects the "virtual path" (the path in the graph). The convex sets and the points in them would not appear in the master problem. The subproblem would be a second order cone program that, for a candidate "virtual path", would compute the shortest corresponding "physical path" (picking the points in the convex sets). If the master problem underestimated the length of the physical path, an "optimality cut" would be added to the master problem and the fun would resume. I have a tentative formulation, but I'm not sure it is useful.

Update: By "popular request", here's my idea. Someone should check my math. First, some terminology. The virtual path is the path in the graph. The physical path is the corresponding sequence of line segments connecting points in the associated convex sets. I'll use $s$ and $t$ to denote the origin and destination of the virtual path, respectively.

Before formulating the master problem, we compute the shortest physical distance corresponding to each edge in $E$. Let $$d_{i,j}=\min\left\{ \left\Vert x_{i}-x_{j}\right\Vert :x_{i}\in S_{i},x_{j}\in S_{j}\right\} \ \forall(i,j)\in E.$$

The master problem involves only the virtual portion (i.e., the graph), not the physical portion. For each edge $(i,j)\in E$ we have a binary variable $y_{i,j}$ that is 1 if and only if that edge is part of the chosen path. We also have a nonnegative variable $w$ that is a surrogate for the length of the physical path. The master problem is: \begin{alignat*}{1} \min & \ \ w\\ \textrm{s.t.} & \sum_{(i,j)\in E}y_{i,j}-\sum_{(j,i)\in E}y_{j,i}=\begin{cases} 1 & i=s\\ -1 & i=t\\ 0 & s\neq i\neq t \end{cases}\forall i\in V\\ & w\ge\sum_{(i,j)\in E}d_{i,j}y_{i,j}\\ & \dots \end{alignat*} where the ellipsis represents Benders cuts (to come). The first set of constraints is the usual path flow stuff; the last constraint is a valid lower bound for any possible path.

The subproblem is a second order cone problem (I think -- someone really should check this as I don't normally mess with SOCPs). The subproblem is constructed around a proposed virtual path $P$. I use $P_V$ to denote the vertices on the path and $P_E$ to denote the edges on the path, both viewed as sets. It uses nonnegative variables $z_{i,j}$ to represent the Euclidean length of the physical segment corresponding to an edge $(i,j)\in P_E$. \begin{alignat*}{1} \min & \sum_{(i,j)\in P_{E}}z_{i,j}\\ \mathrm{s.t.} & \ \ x_{i}\in S_{i}\ \ \forall i\in P_{V}\\ & z_{i,j}\ge\left\Vert x_{i}-x_{j}\right\Vert \ \ \forall(i,j)\in P_{E}. \end{alignat*}

The first constraint ($x_i \in S_i$) has to be translated into linear equality or inequality constraints. (Recall that I assume $S_i$ is polyhedral.) If $S_i$ is given as a set of extreme points (and maybe a set of extreme rays), this entails adding a gaggle of weight variables used to take convex combinations of extreme points and nonnegative combinations of extreme rays. Note that if the virtual path is just a single edge $(i,j)$, this problem can be used to calculate $d_{i,j}$.

The idea is to solve the master problem and get a candidate virtual path $\hat{P}$. You can solve the master to optimality, or if using a solver that supports callbacks you can just go as far as the first (or next) candidate solution. That path is used to construct the subproblem, which is solved to get the actual shortest physical representation of the virtual path. If the surrogate variable matches the physical length, accept the solution (and, if using callbacks, continue). If not, we add the following Benders cut: $$w\ge\hat{f}\left(\sum_{(i,j)\in\hat{P}_{E}}y_{i,j}-\left|\hat{P}_{E}\right|+1\right),$$ where $\hat{f}$ is the optimal objective value of the subproblem (the shortest possible length of the physical path) and $\left|\hat{P}_{E}\right|$ is the number of edges in the virtual path. The Benders cut is guaranteed nonbinding except when a virtual path contains all the edges that the current one does, so it's not a strong cut by any means, but it is valid.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much for the answer. That's something I didn't think of trying. Actually, my sets $S_v$ are polytopic, and deriving a vertex representation might almost be doable (I'm working in 5/10 dimensions). The SOC program part is clear, but at the moment I don't fully see how to setup the master problem. I need to review my Bender's decomposition notes though. If it's not too time consuming, I'd be happy to know more about your tentative formulation of the master problem. $\endgroup$ – Tobia Marcucci Nov 22 at 22:23
  • $\begingroup$ I think its always interesting to see the formulations ! It might give more ideas and inspire someone with a new idea :) $\endgroup$ – Kuifje Nov 23 at 8:21
  • $\begingroup$ Very interesting ! I wish I could upvote twice... $\endgroup$ – Kuifje Nov 23 at 19:24
  • $\begingroup$ @Kuifje Assuming that points from the various $S_v$ can be "sampled" easily, and that the number of points per set were not too large, I suspect that your discretization approach would solve a lot faster than my Benders approach. $\endgroup$ – prubin Nov 23 at 21:14
  • 1
    $\begingroup$ @Kuifje You are correct that it is not "classical" Benders. I don't think it is what most people mean by "logic-based Benders" (but I'm not positive). I'm not sure there is a good term for it. "Benders-like"? Maybe just "row generation" (which is a bit vague). The cut is a variant of the "no good" cut that rules out a binary solution. Rather than saying at least one variable much change, the cut says that if no variable changes, the distance is at least $\hat{f}$. $\endgroup$ – prubin Nov 24 at 23:51
5
$\begingroup$

One way of addressing this problem would be to discretize the sets $S_v$ for each $v \in V$. That is, define a finite number of points within $S_v$, and for each of these points, define a node. Link these nodes to all of the neighbors of node $v$, but adapt the distance with the actual Euclidian distance.

Once you have this new graph, run the classical shortest path algorithm.

For example, suppose you have only one edge in your graph: $G=(\{u,v\},(u,v))$. You want the shortest path from $u$ to $v$. Define nodes $u_1,...,u_n$ to cover set $S_u$, and nodes $v_1,...,v_n$ for $S_v$, and add an edge from each vertex $u_i$ to each vertex $v_j$, with cost $d_{u_i,v_j}$, where $d$ denotes the distance that you are using. You can define a source and link it to each node $u_i$, and a sink that is linked to each $v_j$. Now, the shortest path from $u$ to $v$ is the shortest path from the source to the sink.

If the triangle inequality holds for the distance function, I cannot think of a good reason why it would not be sufficient to only discretize the borders of sets $S_v$. In this case you would save some space and reduce the complexity. However, proving that it is sufficient is yet to be done.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks Kuifje. That's one of the approaches I've been thinking of. Its main issue is the exponential complexity in the size $m$ of the space where the sets $S_v$ live. (The nice thing on the other hand is that you can easily bound the discretization error.) I also came up with a reasonably strong mixed-integer formulation of the problem, but I'm still wondering if one can come up with a better algorithm tailored for this problem? Thanks again! $\endgroup$ – Tobia Marcucci Nov 22 at 17:10
  • $\begingroup$ I think if you wrote your MILP formulation in the question, it could give ideas and you might get more feedback/answers! $\endgroup$ – Kuifje Nov 23 at 8:19
  • $\begingroup$ Yes, I too would like to see the formulation. $\endgroup$ – prubin Nov 23 at 21:12
  • $\begingroup$ Kuifje and prubin, thank you very much for your interest in this problem. Actually, I did some more testing and my formulation seems to be pretty bad. I'll try to fix it, and then I'll write it here. Please give me a few days. I'm going to accept prubin's answer since it both answers the original question (the related literature one) and it also proposes a very nice problem formulation. Thank you both! $\endgroup$ – Tobia Marcucci Nov 23 at 23:34
  • $\begingroup$ I may be wrong, but doesn't the shortest path change directions on the edges of sets $S_v$ ? If this is true (I haven't tried proving it but cannot come up with a simple counter example), you can discretize only the border of $S_v$, saving a bunch of space and reducing the complexity. $\endgroup$ – Kuifje Nov 25 at 19:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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