Shortest path problem with underlying continuous variables

Question

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?

Answer 1

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.

Answer 2

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.