2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are $p$ and $q$ shortest paths? $\endgroup$ – Sasho Nikolov Dec 21 '17 at 15:52
  • $\begingroup$ yes, I am looking for the maximal possible cost difference between two shortest paths $\endgroup$ – Florian K Dec 21 '17 at 16:21
  • 2
    $\begingroup$ What is the role of the upper and lower bounds? What weights do you use to determine the costs of the two paths? Oh, I see: you are saying to choose each edge weight $c_e$ (subject to the upper and lower bounds) so as to maximize the resulting difference $dist_c(s, w) - dist_c(s, v)$. $\endgroup$ – Neal Young Dec 31 '17 at 4:24
  • $\begingroup$ Correct. Basically, the edge weights are uncertain but inside a known interval. The maximization finds a worst case scenario under which the path to $w$ is maximal more expansive then to $v$. $\endgroup$ – Florian K Dec 31 '17 at 15:13
  • $\begingroup$ I’m pretty sure that the problem can be solved in polynomial time. I will post a solution when I have it in a proper format. $\endgroup$ – Florian K Dec 31 '17 at 15:22
1
$\begingroup$
  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.

$\endgroup$
  • $\begingroup$ Looks promising. Can you explain why you think your algorithm is correct? $\endgroup$ – Neal Young Jan 15 '18 at 17:25

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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