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.