Maximum difference between two shortest paths

Question

My problem is the following maximization problem:

Given: A graph $G=(V,E)$, lower bounds $l \in \{0,1,..,K\}^E$ and upper bound $u \in \{0,1,..,K\}^E$ for the edge weights, a source $s$ and two targets $v$ and $w$.

Problem: Compute $$ \max\{ c_p - c_q | p \text{ is a shortest } s,w \text{-path}, q \text{ is a shortest } s,v \text{-path}, c \in [l,u] \} $$ with $c_p$ and $c_q$ being the costs of path $p$ and $q$, respectivly.

I cannot image that that this problem has not been studied, but i cannot find anything. Does someone know the name of this problem and any resources.

Thanks in advance.

The problem can also be formulated as the following bilevel program:

$$ \max ~~~~~~~~~~~~~ c^Tx - c^Ty ~~~~~~~~~~~~~~~~~~~\\ s.t. x \in \arg\min \{ c^Tx| Mx=b^{s,w} \}, \\ ~~~~~~~ y \in \arg\min\{ c^Ty | My=b^{s,v} \}, \\ l \leq c \leq u $$

with $M$ being the vertex-edge incidence matrix of the graph and $b^{s,v},b^{s,w} \in \{0,1\}^V$ defined as follows: , $b_s^{s,v} = b_s^{s,w} = 1$, $b_v^{s,v} = b_w^{s,w} = -1$, and $0$ otherwise.

Answer 1

1. There exists an optimal solution $p,q,c$ such that $c_e = l_e$ for all edges $e$ in the path $q$ and $c_e = u_e$ otherwise.
2. For the optimal solution from point 1 exists a vertex $x$ at which the paths $p$ and $q$ split. The subpath $p^x$ of $p$ from $x$ to $v$ is a shortest path from $x$ to $v$ for the edge weights $u$ (the upper bound).

To solve the problem consider the following procedure:

For all $x \in V$:

• Compute the length of the shortest path from any vertex $y \in V$ to $w$ for the edge weights $u$. The lengths are stored in $d \in \mathbb{N}^V$.
• Define the node potentials $\pi_y = d_x - d_y$.
• Compute the shortest path from $x$ to $v$ that respects the node potentials $\pi$, i.e. choose the edge weights such that the shortest path to $v$ with respect to $c$ is greater or equal to $\pi_y$ for all $y \in V$. This can be done by a modified Dijkstra algorithm. The Dijkstra algorithm normally takes fixed edge weights $c$. We choose the edge weights as follows: $\min\{ c \in [l_e,u_e] \mid \pi_w \leq d(u) + c \}$. Furthermore, make sure to take the shortest path that only uses edges with edge weights at their lower bound if possible.
• If the above procedure finds a shortest path from $x$ to $v$ that only uses edges with edge weights at their lower bound, then $x$ might be a splitting point from point 2. Remember that $x$ as well as the resulting edge costs $c^x$

For all the remembered pairs of vertices $x$ and corresponding edge costs $c^x$, compute the shortest path to $x$, simillar to the shortest path from $x$ to $v$. Now change $c_e^x$ to $l_e$ for all edges in that shortest path. The solution to problem is now given by $$ \max_{x}\{c_p^x - c_q^x \mid p \text{ is a shortest } s,w \text{-path}, q \text{ is a shortest } s,v \text{-path} \}. ~~~~~~~ (1)$$

Illustration of correctness:

Let $\mathcal{D}$ be the domain of the original problem and $p,q,c^x$ the solution of (1), then we have $(p,q,c^x) \in \mathcal{D}$. Hence, the solution of (1) is smaller or equal to the solution of the original problem.

Now let $(p,q,c)$ be the solution of the original problem and let $x$ be the splitting point of the two paths $p$ and $q$. The described procedure considers $x$ and computes the shortest path to $v$, which is exactly $p(x \rightarrow v)$, such that the shortest path $\rho$ to $w$ is the shortest path with respect to the edge weights at their upper bound $u$. We therefore get: $$ c_p - c_q = c_{p(s \rightarrow x)} + c_{p(x \rightarrow w)} - c_{q(s \rightarrow x)} + c_{q(x \rightarrow v)} \\ = c_{p(x \rightarrow w)} - c_{q(x \rightarrow v)} \leq c_{p(x \rightarrow w)} - c_{\gamma}. $$ Hence, the solution of (1) is greater or equal to the solution of the original problem.

To prove the correctness of the modified Dijkstra algorithm, one can modify the original proof.