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

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 ?

• 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.
– D.W.
May 6 at 22:37

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.

• I learned a lot from this answer. Thanks! May 6 at 23:35
• Thanks! Very interesting solution May 7 at 0:18
• @InuyashaYagami, fixed, thank you!
– D.W.
May 7 at 1:47

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.
• There can be exponentially many cuts, so this can give an exponential-size encoding. That doesn't seem very satisfying.
– D.W.
May 6 at 22:54
• @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. May 6 at 22:56
• @InuyashaYagami I've also tried to build ILP using max-flow LP formulation, think it could be useful here May 6 at 23:12
• @InuyashaYagami can you please explain your ideas about solution with the polynomial number of constraints? May 6 at 23:19
• @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/…). May 6 at 23:22