Minimize overlap penalty between paths in graph

Question

Suppose we have a weighted undirected graph $G(V,E)$. We are given the information that $V_a \cap V_b = \emptyset$ and $V_a,V_b \subset V$.

We want to find paths from all vertices in $V_a$ to all vertices in $V_b$ given the following conditions:

• Primary objective: paths minimize the number of shared edges
• Secondary objective: sum of weighted path lengths are minimized
• Sharing an edge gives a penalty equivalent to the weight of the shared edge
  • Consider the following example:
    1. If path $s_1 - t_1$, $s_2 - t_1$, and $s_3 - t_1$ all use edge $e_2$ then the penalty is $3\cdot weight(e_2)$.
• Paths from any particular $s \in V_a$ to all $t \in V_b$ do not acquire a penalty for overlapping with other paths from that particular $s$. That is to say paths from $s_i$ to $t_j$ for all $t_j \in V_b$ cannot acquire a penalty from each other.
  • Consider the following examples:
    2. If path from $s_1$ to $t_1$ uses edges $e_1, e_2, e_3$ and path from $s_1$ to $t_2$ uses the edges $e_1, e_2, e_4$, then there is no penalty.
    3. If path from $s_1$ to $t_1$ uses edges $e_1, e_2, e_3$ and path from $s_2$ to $t_2$ uses the edges $e_1, e_2, e_4$, then there is a penalty of $\mathit{weight}(e_1) + \mathit{weight}(e_2)$.

Pictured Example:

In the pictured example we can find the following solutions for each of the desired six paths:

• $s_1 - t_1$: $s_1,a,t_1$
• $s_1 - t_2$: $s_1,a,t_2$
  • note there is no penalty for sharing the edge $(s_1,a)$ because both paths so far both start from $s_1$
• $s_2 - t_1$: $s_2,b,a,t_1$
  • Note this would have a penalty for sharing edge $(a,t_1)$ with the path from $s_1-t_1$
• $s_2 - t_2$: $s_2,b,a,t_2$
  • Note there is no penalty from this path
• $s_3 - t_1$: $s_3,c,t_1$
  • Note this has no penalty and we could have chosen path $s_3,c,d,t_1$ for no penalty as well, but it is a longer path so we don't choose it
• $s_3 - t_2$: $s_3,c,d,t_2$
  • Note this has no penalty no matter what path was chosen for $s_2-t_1$

The practical application of this problem is loosely defined. These constraints are not rigid if they cause too many complications. For example, instead of having the penalty in the first example being $3 \cdot \mathit{weight}(e_3)$ it might be acceptable to have the penalty as $\mathit{weight}(e_3)$. I'm mostly looking for new ideas to handle this or a slight variation of this problem.

This is an extension to Algorithm for finding minimally overlapping paths in a graph

Answer 1

You can formulate this as a multicommodity flow problem and solve it via linear programming. The commodities are $K = V_a \times V_b$. Let $A$ be the arc set, with one arc in each direction for each edge in $E$. For $(i,j)\in A$ and $k\in K$, let variable $x_{i,j}^k \ge 0$ be the flow along arc $(i,j)$ of commodity $k$. For $\{i,j\}\in E$ and source node $s\in V_a$, let variable $z_{i,j}^s \ge 0$ be the maximum amount of flow (in either direction) across edge $\{i,j\}$. Let variable $y_{i,j}\ge 0$ be the excess number of sources that use edge $\{i,j\}\in E$. Let $b_{i,k}$ be the supply at node $i$ of commodity $k$; explicitly, $b_{i,k}$ is $1$ for the source node of commodity $k$, $-1$ for the sink node of commodity $k$, and $0$ otherwise. Let $c_{i,j}$ be the weight of edge $\{i,j\}$. The primary problem is to minimize $\sum_{\{i,j\}\in E} c_{i,j} y_{i,j}$ subject to: \begin{align} x_{i,j}^k + x_{j,i}^k &\le z_{i,j}^s &&\text{for all $\{i,j\}\in E$ and $k=(s,t)\in K$}\tag1\\ \sum_{s:(s,t)\in K} z_{i,j}^s &\le 1 + y_{i,j} &&\text{for all $\{i,j\}\in E$}\tag2\\ \sum_j (x_{i,j}^k - x_{j,i}^k) &= b_{i,k} &&\text{for all $i\in V$ and $k\in K$}\tag3 \end{align} The secondary problem is to minimize $\sum_{(i,j)\in A}\sum_{k\in K} c_{i,j} x_{i,j}^k$ subject to $(1),(2),(3)$ and: $$\sum_{\{i,j\}\in E} c_{i,j} y_{i,j} \le p^*,$$ where $p^*$ is the optimal primary objective value.