1
$\begingroup$

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 ?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    May 6 at 22:37
2
$\begingroup$

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.

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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