Linear program for min-length pair of edge-disjoint paths problem

Question

Consider a problem: we have an undirected graph $G = (V, E)$, function $l: E \to \mathbb{Z}_{+}$ where $l(e)$ is edge's length $e \in E$, and two vertices $s$ and $t$. And we want to find a pair $(A, B)$ of edge-disjoint paths between $s$ and $t$ such that $$ \sum_{e \in A}l(e) + \sum_{e \in B} l(e) \to \min $$ How can I formulate this problem in terms of ILP ?

• D.W.: Can you tell us the context where you encountered this task? Is it a practical problem? Did you encounter it in a textbook or exercise? Is there any particular reason you want a solution using ILP specifically? What approaches to encoding as ILP have you considered and what difficulties did you encounter? cs.stackexchange.com/q/12102/755 may be useful.

Answer 1

I think this can be solved in polynomial time by finding a minimum-cost maximum flow in the graph, where you set the capacity of each edge to 1ドル$ and the cost of each edge $e$ to $-l(e)$, and add a source node $s_0$ with an edge $s_0 \to s$ of capacity 2 and cost 0. (You might need to add a "demand" that the edge $s_0 \to s$ has exactly 2 units of flow along it.)

If you must formulate it as an ILP, introduce a zero-or-one variable $x_e$ for each edge, with the intended semantics that $x_e=1$ means that edge $e$ is in the first path. Add a constraint that, for each vertex $v$ other than the source/sink, $\sum_w x_{(v,w)}$ is 0 or 2; for the source and sink, it must be 1. This captures the requirement that you have a path from $s$ to $t$. Add another zero-or-one variable $y_e$ for each edge, with similar constraints to ensure it represents a path from $s$ to $t$. Finally, enforce the disjointness requirement: $x_e + y_e \le 1$. The objective function to maximize is $\sum_e l(e) x_e + l(e) y_e$.

You can enforce a constraint that a variable $z$ is 0 or 2 by requiring $z=2t$ where 0ドル\le t \le 1$ is a fresh zero-or-one integer variable.

• Inuyasha Yagami: I learned a lot from this answer. Thanks!
• envy grunt: Thanks! Very interesting solution

Answer 2

Optimization Function: minimize $\sum_{e \in E} l(e) \cdot x_{1}(e) + \sum_{e \in E} l(e) \cdot x_{2}(e)$

Constraints: $$\sum_{(u,v) \in C} x_{1}(u,v) \geq 1 \quad \textrm{for every $(s,t)$ cut $C$ in the graph}$$ $$\sum_{(u,v) \in C} x_{2}(u,v) \geq 1 \quad \textrm{for every $(s,t)$ cut $C$ in the graph}$$ $$x_{1}(u,v) + x_{2}(u,v) \leq 1 \quad \textrm{for every edge $(u,v) \in E$}$$ $$x_{1}(u,v), x_{2}(u,v) \in \{0,1\} \quad \textrm{for every edge $(u,v) \in E$}$$ Correctness:

• For an edge $e = (u,v)$, $x_{1}(e) = 1$ denotes if $e$ is in the path $A$; otherwise $x_{1}(e) = 0$. Similarly, $x_{2}(e) = 1$ denotes if $e$ is in the path $B$; otherwise $x_{1}(e) = 0$. Note that I have used the variables $x_{1}(e)$ and $x_{1}(u,v)$ interchangebly.
• The first constraint is for path $A$ from $s$ to $t$.
• The second constraint is for path $B$ from $s$ to $t$.
• The third constraint makes the paths $A$ and $B$ disjoint.

• D.W.: There can be exponentially many cuts, so this can give an exponential-size encoding. That doesn't seem very satisfying.
• Inuyasha Yagami: @D.W. Agreed. I am trying to think of a solution with the polynomial number of constraints. That might require the shortest path LP formulation that indeed has the polynomial number of constraints.
• envy grunt: @InuyashaYagami I've also tried to build ILP using max-flow LP formulation, think it could be useful here
• envy grunt: @InuyashaYagami can you please explain your ideas about solution with the polynomial number of constraints?
• Inuyasha Yagami: @envygrunt It is possible to formulate the shortest path problem from $(s,t)$ using an LP with the polynomial number of constraints. See Section 29.2 of CLRS (link: edutechlearners.com/download/…).